perm filename V2R.IN[TEX,DEK] blob
sn#336059 filedate 1978-02-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00013 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 763 galleys 1-2 NOTE: the end of 1 and beginning of 2 were unreadable.
C00021 00003 folio 768 galley 3
C00039 00004 folio 770 galley 4
C00053 00005 folio 772 galley 5
C00069 00006 folio 776 galley 6
C00085 00007 folio 777 galley 7 WARNING: Couldn't read the beginning of this galley.
C00096 00008 folio 781 galley 8
C00110 00009 folio 784 galley 9
C00129 00010 folio 790 galley 10
C00145 00011 folio 794 galley 11
C00164 00012 folio 797 galley 12
C00182 00013 folio 800 galley 13
C00194 ENDMK
C⊗;
folio 763 galleys 1-2 NOTE: the end of 1 and beginning of 2 were unreadable.
0 {U0}{H9L11M29}58320#Computer Programming!(Knuth/A.-W.)!ch.
2 4!f. 763!g. 1c|'{A24}{H10}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨3|∨
5 .|∨3|'{A12}{H9}{M21}|∂!!!!!!!|∂!!!!!!!|∂!!!!!!!|∂!!!!!!!|∂|E
6 |n|;|>|9|1|≡1|≡.|4|927|4α⊗↓|447:|'18|4α⊗↓|442:|;
10 09|4α⊗↓|405:|;2718|4α⊗↓|44742:|;>|>!!|1|108|4|4|4|4|4|;
15 04|4|4|4|4|4|;00|4|4|4|4|4|;1269!!|4|;>|>|1|1!!|1|908|1|9|;
21 04|;00|;!|1|11269|4|4|4|4|4|;>|>|1|1!!15|;14|;
28 45|;|4|1|1|1|→α_↓0045|4|4|4|4|4|;>|>|1|1!!49|;
33 16|;45|;0756|;>|>|1|1!!|4|4|4|4|449|;|4|4|4|4|416|;
40 |4|4|4|4|445|;!!|40756|;>{A4}|>|1|1!!1269|;0756|;
46 0045|;12888756|;>{A12}|9|1|≡2|≡.|4|9K{H9}|v4|εQ|4α+↓|4|"l|¬K
49 Q|"L|)|4|¬E|4{H10}|¬K{H9}|v4Q|4α+↓|4|¬KQ|)|4|¬W|4{H10}|¬K{H9
49 }|v4Q|4α+↓|42|¬KQ|4α+↓|41|)|4α=↓|4|¬K|v4Q|)|4α+↓|41,
50 |πso |ε|"l|¬K|v4Q|4α+↓|4R|)|"L|4|¬E|4|"l|¬K|v4Q|)|"L|4α+↓|41
51 .|'{A3}{H9L11M29}|π|9|1|≡3|≡.|4|9When |εk|4|¬E|42,
54 |πthe result is true, so assume that |εk|4|¬Q|42.
62 |πLet |εq|βk|4α=↓|42|gQ|rk, r|βk|4α=↓|42|gR|rk,
65 |πso that |εR|βk|4α=↓|4|"l|¬K|v4Q|βk|)|"L |πand
69 |εQ|βk|4α=↓|4Q|βk|βα_↓|β1|4α+↓|4R|βk|βα_↓|β1.
70 |πWe must show that |ε1|4α+↓|4(R|βk|4α+↓|41)2|gR|rk|4|¬E|42|
74 gQ|rk|rα_↓|r1; |πthis inequality isn't close
79 at all, one way is to observe that |ε1|4α+↓|4(R|βk|4α+↓|41)2
87 |gR|rk|4|¬E|41|4α+↓|42|g2|gR|rk |πand |ε2R|βk|4|¬W|4Q|βk|βα_
89 ↓|β1 |πwhen |εk|4|¬Q|42. |π(The fact that |ε2R|βk|4|¬W|4Q|βk
95 |βα_↓|β1 |πis readily proved by induction since
102 |εR|βk|βα+↓|β1|4α_↓|4R|βk|4|¬E|41 |πand |εQ|βk|4α_↓|4Q|βk|βα
104 _↓|β1|4|¬R|42.)|'{A3}|π|9|1|≡4|≡.|4|9For |εj|4α=↓|41,|4.|4.|
106 4.|4,|4r, |πcalculate |εU|βe(j|g2), jU|βo(j|g2),
110 V|βe(j|g2), jV|βo(j|g2); |πand by recursively
115 calling the multiplication algorithm, calculate|'
120 {A9}|h|εW(|→α_↓j)|4|∂α=↓|4(U|βe(j|g2)|4α_↓|4jU|βo(j|g2))(V|β
120 e(j|g2)|4α_↓|4jV|βo(j|g2));|E|n|;| W(j)|4|Lα=↓|4{H11}({H9}U|
121 βe(j|g2)|4α+↓|4jU|βo(j|g2){H11})({H9}V|βe(j|g2)|4α+↓|4jV|βo(
121 j|g2){H11}){H9},>{A4}| W(|→α_↓j)|4|Lα=↓|4{H11}({H9}U|βe(j|g2
122 )|4α_↓|4jU|βo(j|g2){H11})({H9}V|βe(j|g2)|4α_↓|4jV|βo(j|g2){H
122 11}){H9};>{A9}|πand then we have |εW|βe(j|g2)|4α=↓|4|f1|d32|
127 ){H11}({H9}W(j)|4α+↓|4W(|→α_↓j){H11}){H9}, W|βo(j|g2)|4α=↓|4
128 |f1|d32|){H11}({H9}W(j)|4α_↓|4W(|→α_↓j){H11}){H9}.
129 |πAlso calculate |εW|βe(0)|4α=↓|4U(0)V(0). |πNow
133 construct di=erence tables for |εW|βe |πand |εW|βo,
140 |πwhich are polynomials whose respective degrees
146 are |εr |πand |εr|4α_↓|41.|'|π!!|1|1This method
152 reduces the size of the numbers being handled,
160 and reduces the number of additions and multiplications.
168 Its only disadvantage is a longer program (since
176 the control is somewhat more complex, and some
184 of the calculations must be done with signed
192 numbers).|'{H9L11M29}!!|1|1Another possibility
195 would perhaps be to evaluate |εW|βe |πand |εW|βo
203 |πat 1|g2, 2|g2, 4|g2,|4.|4.|4.|4, (2|ε|gr)|g2;
208 |πalthough the numbers involved are larger, the
215 calculations are faster, since all multiplications
221 are replaced by shifting and all divisions are
229 by binary numbers of the form |ε2|gj(2|gk|4α_↓|41).
236 (|πSimple procedures are available for dividing
242 by such numbers.)|'{A3}|π|9|1|≡5|≡.|9|4Start
246 the |εq, r |πsequences out with |εq|β0, q|β1
254 |πlarge enough so that the inequality in exercise
262 3 is valid. Then we will _nd in the formulas
272 analogous to those preceding Theorem C that |ε|≤h|β1|4|¬M|40
279 |πand |ε|≤h|β2|4α=↓|4(1|4α+↓|41/2r|βk)2|ur1|4α+↓|4|¬H2Q|βkα
281 _↓|¬H2Q|βk|βα+↓|β1|)|)(Q|βk/Q|βk|βα+↓|β1). |πThe
283 factor |εQ|βk/Q|βk|βα+↓|β1|4|¬M|41 |πas |εk|4|¬M|4|¬X,
287 |πso we can ignore it if we want to show |ε|≤h|β2|4|¬W|41|4α
297 _↓|4|≤e |πfor all large |εk. |πNow |ε|¬H|v42Q|βk|βα+↓|β1|)|4
303 α=↓|4{H10}|¬H{H9}|v42Q|βk|4α+↓|42|"p|¬H2Q|βk|"P|4α+↓|42|)|4|
303 ¬R|4{H10}|¬H{H9}|v4(2Q|βk|4α+↓|42|¬H2Q|βk|4α+↓|41)|4α+↓|41|4
303 |¬R|4|¬H2Q|βk|4α+↓|41|4α+↓|41/3R|βk. |πHence
305 |ε|≤h|β2|4|¬E|4(1|4α+↓|41/2r|βk)2|gα_↓|g1|g/|g3|gR|rk,
306 |πand lg |ε|≤h|β2|4|¬W|40 |πfor large enough
312 |εk.|'!!|1|1Note|*/: |\|πAlgorithm C can also
318 be modi_ed to de_ne a sequence |εq|β0, q|β1,|4.|4.|4.
326 |πof a similar type which is based on |εn, |πso
336 that |εn|4|¬V|4q|βk|4α+↓|4q|βk|βα+↓|β1 |πafter
339 step C1. (Algorithm S essentially does this.)
346 This would establish (19).|'{A3}{A3}{H9L11M29}|9|1|≡6|≡.|9|4
350 Any common divisor of |ε6q|4α+↓|4d|β1 |πand |ε6q|4α+↓|4d|β2
357 |πmust also divide their di=erence |εd|β2|4α_↓|4d|β1.
363 |πThe (|f6|d52|)) di=erences are 2, 3, 4, 6,
371 8, 1, 2, 4, 6, 1, 3, 5, 2, 4, 2, |πso we must
385 only show that at most one of the given numbers
395 is divisible by each of the primes 2, 3, 5. Clearly
406 only |ε6q|4α+↓|42 |πis even, and only |ε6q|4α+↓|43
413 |πis a multiple of 3; and there is at most one
424 multiple of 5, since |εq|βk|4|=|↔6|"o|43 (|πmodulo
430 5).|'{A3}|9|1|≡7|≡.|9|4|εt|βk|4|¬E|46t|βk|βα_↓|β1|4α+↓|4ck3|
431 gk |πfor some constant |εc; |πso |εt|βk/6|gk|4|¬E|4t|βk|βα_↓
437 |β1/6|gk|gα_↓|g1|4α+↓|4ck/2|gk|4|¬E|4t|β0|4α+↓|4c|4|¬K|ur|)j
437 |¬R1|4(j/2|gj)|4α=↓|4M. |πThus |εt|βk|4|¬E|4M|4|¬O|46|gk.|'
440 {A3}|π|9|1|≡8|≡.|4|9The analog of Eq. (39) would
446 break down. In fact it is impossible to ``untransform''
455 the _nite Fourier transform of (|εa|β0, a|β1,
462 a|β2, a|β3) |πmod 15 when |ε|≤v|4α=↓|42, |πsince
469 information is lost during the transformation
475 process.|'{A3}|9|1|≡9|≡.|9|4|εKu|ur|)(|→α_↓r)|4|πmod|4|εK|).
476 |'{A3}|π|≡1|≡0|≡.|4|9The lower bound ensures
481 that |ε|λ3|4α+↓|42|4|¬W|4n, |πso the products
486 |ε|=#U|βt|=#V|βt |πhave fewer bits than the product
493 |εuv. |πThe upper bound comes from the de_nition
501 of |ε|≤v. |π[Sch|=4onhage observes that we could
508 actually allow |εk|4α=↓|4|λ3|4α+↓|44, |πsince
512 |ε(2|g3|g|¬O|g2|in|iα_↓|i2|4α_↓|42|g2|in|iα_↓|i2)|g2|4|"o|42
512 |4(|πmodulo 2|g2|i|εn|4α+↓|41).]|'{A3}|π|≡1|≡1|≡.|4|9An
515 automaton cannot have |εz|β2|4α=↓|41 |πuntil
520 it has |εc|4|¬R|42, |πand this occurs _rst for
528 |εM|βj |πat time |ε3j|4α_↓|41. |πIt follows that
535 |εM|βj |πcannot have |εz|β2z|β1z|β0|4|=|↔6α=↓|4000
539 |πuntil time |ε3(j|4α_↓|41). |πFurthermore, if
544 |εM|βj |πhas |εz|β0|4|=|↔6α=↓|40 |πat time |εt,
550 |πwe cannot change this to |εz|β0|4α=↓|40 |πwithout
557 a=ecting the output; but the output cannot be
565 a=ected by this value of |εz|β0 |πuntil at least
574 time |εt|4α+↓|4j|4α_↓|41, |πso we must have |εt|4α+↓|4j|4α_↓
580 |41|4|¬E|42n. |πSince the _rst argument we gave
587 proves that |ε3(j|4α_↓|41)|4|¬E|4t, |πwe must
592 have |ε4(j|4α_↓|41)|4|¬E|42n, |πthat is, |εj|4α_↓|41|4|¬E|4n
596 /2, |πi.e., |εj|4|¬E|4|"ln/2|"L|4α+↓|41.|'|π!!|1|1Furthermor
599 e, this is the best possible bound, since the
608 inputs |εu|4α=↓|4v|4α=↓|42|gn|4α_↓|41 |πrequire
611 the use of |εM|βj |πfor all |εj|4|¬E|4|"ln/2|"L|4α+↓|41.
618 |π(For example, note from Table 1 that |εM|β2
626 |πis needed to multiply two-bit numbers, at time
634 3.)|'{A3}*?|≡1|≡3|≡.|9|4If it takes |εT(n) |πcycles
640 to multiply |εn-|πbit numbers, we can accomplish
647 the multiplication of |εm-|πbit by |εn-|πbit
653 by breaking the |εn-|πbit number into |"p|εn/m|"P
660 m-|πbit groups, using |ε|"pn/m|"PT(m)|4α+↓|4O(n|4α+↓|4m)
664 |πoperations. The results of this section therefore
671 give an estimated running time of |εO(n|4|πlog|4|εm|4|πlog|4
677 log|4|εm).|'{A24}{H10L12M29}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|1|∨4|∨
678 .|∨4|'{A12}{H9L11M29}|9|1|≡1|≡.|4|9We compute
681 {H11}({H9}|¬O|4|¬O|4|¬O|4(|εa|βmb|βm|βα_↓|β1|4α+↓|4a|βm|βα_↓
681 |β2)b|βm|βα_↓|β2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|β1{H11}){H9
681 }b|β1|4α+↓|4a|β0 |πby adding and multiplying
686 in the |εB|βj-|πsystem.|'{A9}{M25.6}|∂!!!!!!!!!|∂!!|∂!!!!!!|
689 ∂!!!!!|∂!!!!!|∂!!!!!!!|∂|E|;|>|;T.|;α=↓|420(cwt.|;
694 α=↓|48(st.|;α=↓|414(lb.|;α=↓|416|4oz.)))|;>{A2}|>
699 Start|4with|4zer|>Divide|4by|4|¬X|'0|;0|;|9|10|;
704 |9|10|;Remainder|4α=↓|48|;>{A12}|εAnswer|*/: |\|π8|4T.
709 3|4cwt. 1|4st. 2|4lb. 5|4oz.|'{A3}|9|1|≡3|≡.|9|4[|εCACM
714 |≡2|≡, 7 (|πJuly, 1959), 27.]|'{I3.2H}{H9L11M29}!!|1|1(Note|
719 */:|\ |πIt is possible for this algorithm to yield
728 |εU|4α=↓|41; |πif this is undesirable, we could
735 modify the algorithm as follows: In step A1,
743 set a new variable |εt|4|¬L|41. |πIn step A2,
751 do not go to A4 if |εt|4α=↓|41. |πIn step A3,
761 set |εt|4|¬L|40 |πif |εU|βα_↓|βk|4|=|↔6α=↓|4B|4α_↓|41.
765 |πThe re{A9}|ε1/10|4α_↓|42|gα_↓|g3|g5|4|¬W|4|≤a|4α=↓|4(.0001
766 10011001100110011001100110011)|β2|4|¬W|41/10,|;
767 {A9}|πwe _nd that |ε|≤au|4α_↓|4|≤e|4|¬E|4v|4|≤E|4|≤au
771 |πat the end of the computation, where|'{A9}|ε|≤e|4α=↓|4|f7|
778 d38|)|4α+↓|4(.100010001010100011001000101010001)|β2|4|¬W|4|f
778 3|d32|).|;{A9}|πHence |εu/10|4α_↓|42|4|¬W|4u/10|4α_↓|4{H11}(
780 {H9}|≤e|4α+↓|4(1/10|4α_↓|4|≤a)u{H11}){H9}|4|¬E|4v|4|¬E|4|≤au
780 |4|¬W|4u/10. |πSince |εv |πis an integer, the
787 proof is complete.|'{A3}|≡1|≡0|≡.|4|9(a) Shift
792 right one; (b) Extract left bit of each group;
801 (c) Shift result of (b) right two; (d) Shift
810 result of (c) right one, and add to result of
820 (c); (e) Subtract result of d from result of
829 (a).|'{A3}|h|π11.|9|4|∂|→α_↓|4|1|∂o0o0o0|E|n|'
831 |≡1|≡1|≡.|L|L5.7|4|17|4|12|4|11>|L|→α_↓|4|11|4|10>
833 {A4}|L|L4|4|17.7|4|12|4|11>|L|→α_↓|4|1|9|1|1|49|4|14>
835 {A4}|L|L3|4|18|4|13.2|4|11>|L|→α_↓|4|1|9|1|1|47|4|16|4|16>
837 {A4}|L|L3|4|10|4|16|4|16.1>|L|→α_↓|9|1|1|46|4|11|4|13|4|12>
839 {A4}|L|L2|4|14|4|15|4|12|4|19!!|εAnswer|*/:|4|1|\|π(24529)|β1
839 |β0.|'{A3}{H9L11M29}|≡1|≡2|≡.|9|4First convert
842 the ternary number to nonary (radix 9) notation,
850 then proceed as in octal-to-decimal conversion
856 but without doubling. Decimal to nonary is similar.
864 In the given example, we have|'{A12}|h|π|→α_↓|4|1|∂poikiop|E
870 |n|'|L1.7|4|16|4|14|4|17|4|12|4|13>|→α_↓|1|4|1|9|1|41>
873 {A4}|L1|4|16.6|4|14|4|17|4|12|4|13>|→α_↓|4|1|1|9|1|41|4|16>
875 {A4}|L1|4|15|4|10.4|4|17|4|12|4|13>|→α_↓|1|4|1|9|1|41|4|15|4
876 |10>{A4}|L1|4|13|4|15|4|14.7|4|12|4|13>|→α_↓|1|9|1|4|1|41|4|
878 13|4|15|4|14>{A4}|L1|4|12|4|11|4|19|4|13.2|4|13>
880 |→α_↓|1|9|1|4|1|41|4|12|4|11|4|19|4|13>{A4}|L1|4|10|4|19|4|1
881 7|4|13|4|19.3>|→α_↓|1|9|1|4|1|41|4|10|4|19|4|17|4|13|4|19>
883 {A4}|L|1|9|1|49|4|18|4|17|4|16|4|15|4|14!!|εAnswer|*/:|4|1|\|
883 π(987654)|β1|β0.|'{A12}|L|1|9|1|49.8|4|17|4|16|4|15|4|14>
885 |→α+↓|4|1|9|1|9|1|1|4|1|49|'{A4}|L1|4|11|4|18.7|4|16|4|15|4|
886 14>|→α+↓|1|4|1|9|1|41|4|11|4|18|'{A4}|L1|4|13|4|11|4|16.6|4|
888 15|4|14>|→α+↓|1|4|1|9|1|41|4|13|4|11|4|16|'{A4}|L1|4|14|4|14
890 |4|18|4|13.5|4|14>|→α+↓|4|1|1|9|4|11|4|14|4|14|4|18|4|13|'
892 {A4}|L1|4|16|4|10|4|14|4|12|4|18.4>|→α+↓|1|4|1|9|1|41|4|16|4
893 |10|4|14|4|12|4|18|'{A4}|L1|4|17|4|16|4|14|4|17|4|12|4|13!!|
894 εAnswer|*/:|4|1|\|π(1764723)|β9.|'{A12}{H9L11M29}|H*?{U0}{H10L
folio 768 galley 3
895 12M29}58320#Computer Programming!(Knuth/A.-W.)!f.
897 768!ch. 4!g. 3c|'{A12}{H9L11M29}|∂!!|1|1|∂!!!!|∂!!!!|∂!!!!!!
900 !!!!!!!|∂!!!!!!!!!!!!!!!|9|1|∂|E|;|>|≡1|≡3|≡.|'
903 |¬b|¬u|¬f|¬1|'|¬a|¬l|¬f|'.|'(Radix|4point|4on|4_rst|4line)|'
907 >|>|;|;|¬o|¬r|¬i|¬g|'|9|1|1|≤%|¬2|¬3|'|;>|>|;
917 |¬b|¬f|¬2|'|¬o|¬r|¬i|¬g|'|9|1|1|≤%|¬2|¬4|'>|>
922 |;|¬s|¬t|¬a|¬r|¬t|'|¬j|¬o|¬v|'|¬o|¬f|¬l|¬o|'Ensure|4over⊗ow|
926 4is|4o=.|'>|>|;|;|¬e|¬n|¬t|¬2|'|¬b|¬u|¬f|¬1|¬-|¬b|¬u|¬f|¬2|'
933 Set|4bu=er|4pointer.|'>|>|;|¬8|¬h|'|¬e|¬n|¬t|¬3|'
939 |¬1|¬0|'Set|4loop|4counter.|'>|>|;|¬1|¬h|'|¬e|¬n|¬t|¬1|'
946 |εm|'|πBegin|4multiplication|4routine.|'>|>|;
951 |;|¬e|¬n|¬t|¬x|'|¬0|'>|>|;|¬2|¬h|'|¬s|¬t|¬x|'
959 |¬c|¬a|¬r|¬r|¬y|'>|>|;|;.|4.|4.|'|;(See|4exercise|44.3.1<13,
966 |4with|'>|>|;|;|¬j|¬i|¬p|'|¬2|¬b|'!|εv|4α=↓|410|g9|4|πand|4|
973 ¬w|4α=↓|4|¬u.)|'>|>|;|;|¬s|¬l|¬a|¬x|'|¬5|'rA|4|¬M|4next|4nin
980 e|4digits.|'>|>|;|;|¬c|¬h|¬a|¬r|'|;|;>|>|;|;|¬s|¬t|¬a|'
993 |¬b|¬u|¬f|¬2|¬,|¬2|≤#|¬2|¬.|¬5|≤#|'Store next|4nine|4digits.
995 |'>|>|;|;|¬s|¬t|¬x|'|¬b|¬u|¬f|¬2|≤%|¬1|¬,|¬2|'
1002 >|>|;|;|¬i|¬n|¬c|¬2|'|¬2|'Increase|4bu=er|4pointer.|'
1009 >|>|;|;|¬d|¬e|¬c|¬3|'|¬1|'>|>|;|;|¬j|¬3|¬p|'|¬1|¬b|'
1021 Repeat|4ten|4times.|'>|>|;|;|¬o|¬u|¬t|'|¬b|¬u|¬f|¬2|¬-|¬2|¬0
1027 |¬,|¬2|≤#|¬p|¬r|¬i|¬n|¬t|¬e|¬r|≤&|'>|>|;|;|¬j|¬2|¬p|'
1033 |¬d|¬o|¬n|¬e|'Have|4we|4printed|4both|4lines?|'
1035 >|>|;|;|¬e|¬n|¬t|¬2|'|¬0|'Set|4bu=er|4pointer|4for|42nd|4bu=
1041 er.|'>|>|;|;|¬j|¬m|¬p|'|¬8|¬b|'>{A3}{H9L11M29}|≡1|≡4|≡.|4|9L
1049 et |εK(n) |πbe the number of steps required to
1058 convert an |εn-|πdigit decimal number to binary
1065 and at the same time to compute the binary representation
1075 of 10|g|εn. |πThen we have |εK(2n)|4|¬E|42K(n)|4α+↓|4O{H11}(
1080 {H9}M(n){H11}){H9}. Proof|*/: |\|πGiven the number
1085 |εU|4α=↓|4(u|β2|βn|βα_↓|β1|4.|4.|4.|4u|β0)|β1|β0,
1086 |πcompute |εU|β1|4α=↓|4(u|β2|βn|βα_↓|β1|4.|4.|4.|4u|βn)|β1|β
1087 0 |πand |εU|β0|4α=↓|4(u|βn|βα_↓|β1|4.|4.|4.|4u|β0)|β1|β0
1090 |πand 10|ε|gn, |πin |ε2K(n) |πcycles, then compute
1097 |εU|4α=↓|410|gnU|β1|4α+↓|4U|β0 |πand |ε10|g2|gn|4α=↓|410|gn|
1099 4|¬O|410|gn |πin |εO{H11}({H9}M(n){H11}){H9}
1102 |πcycles. It follows that |εK(2|gn)|4α=↓|4O{H11}({H9}M(2|gn)
1106 |4α+↓|42M(2|gn|gα_↓|g1)|4α+↓|44M(2|gn|gα_↓|g2)|4α+↓|4|¬O|4|¬
1106 O|4|¬O{H11}){H9}|4α=↓|4O{H11}({H9}nM(n){H11}){H9}.|'
1107 {H9L11M29}|π!!|1|1(Similarly, Sch|=4onhage has
1110 observed that we can convert a (2|ε|gn|4|πlg|β2
1117 10)-bit number |εU |πfrom binary to decimal,
1124 in |εO{H11}({H9}nM(2|gn){H11}){H9} |πsteps. First
1128 form |εV|4α=↓|410|g2|in|iα_↓|i1 |πin |εO{H11}({H9}M(2|gn|gα_
1131 ↓|g1)|4α+↓|4M(2|gn|gα_↓|g2)|4α+↓|4|¬O|4|¬O|4|¬O{H11}){H9}|4α
1131 =↓|4O{H11}({H9}M(2|gn)) |πsteps, then compute
1135 |εU|β0|4α=↓|4(U |πmod |εV) |πand |εU|β1|4α=↓|4|"lU/V|"L
1140 |πin |εO{H11}({H9}M(2|gn)) |πfurther steps, then
1145 convert |εU|β0 |πand |εU|β1.)|'{A3}|π|≡1|≡8|≡.|4|9Let
1150 |εU|4α=↓|4|πround|ε|βB(u,|4P) |πand |εv|4α=↓|4|πround|ε|βb(U
1152 ,|4p). |πWe may assume that |εu|4|=|↔6α=↓|40,
1158 |πso that |εU|4|=|↔6α=↓|40 |πand |εv|4|=|↔6α=↓|40.
1163 Case |*/|↔O|\ v|4|¬W|4u: |πDetermine |εe |πand
1169 |εE |πsuch that |εb|ge|gα_↓|g1|4|¬W|4u|4|¬E|4b|ge,
1173 B|gE|gα_↓|g1|4|¬E|4U|4|¬W|4B|gE. |πThen |εu|4|¬E|4b|gp|gα_↓|
1175 geu|4|¬E|4U|4α+↓|4|f1|d32|)B|gE|gα_↓|gP |πand
1177 |εU|4|¬E|4u|4α_↓|4|f1|d32|)b|ge|gα_↓|gp; |πhence
1179 |εB|gP|gα_↓|g1|4|¬E|4B|gP|gα_↓|gEU|4|¬W|4B|gP|gα_↓|gEu|4|¬E|
1179 4b|gp|gα_↓|geu|4|¬E|4b|gp. Case |*/|↔P|\, v|4|¬Q|4u:
1183 |πDetermine |εe |πand |εE |πsuch that |εb|ge|gα_↓|g1|4|¬E|4u
1189 |4|¬W|4b|ge, B|gE|gα_↓|g1|4|¬W|4U|4|¬E|4B|gE.
1191 |πThen |εu|4|¬R|4U|4α_↓|4|f1|d32|)B|gE|gα_↓|gP
1193 |πand |εU|4|¬R|4u|4α+↓|4|f1|d32|)b|ge|gα_↓|gp;
1195 |πhence |εB|gP|gα_↓|g1|4|¬E|4B|gP|gα_↓|gE(U|4α_↓|4B|gE|gα_↓|
1196 gP)|4|¬W|4B|gP|gα_↓|gEu|4|¬E|4b|gp|gα_↓|geu|4|¬W|4b|gp.
1197 |πThus we have proved that |εB|gP|gα_↓|g1|4|¬W|4b|gp
1203 |πwhenever |εv|4|=|↔6α=↓|4u.|'|π!!|1|1Conversely,
1206 if |εB|gP|gα_↓|g1|4|¬W|4b|gp, |πthe above proof
1211 suggests that the most likely example for which
1219 |εu|4|=|↔6α=↓|4v |πwill occur when |εu |πis a
1226 power of |εb |πand at the same time it is close
1237 to a power of |εB. |πWe have |εB|gP|gα_↓|g1b|gp|4|¬W|4B|gP|g
1244 α_↓|g1b|gp|4α+↓|4|f1|d32|)b|gp|4α_↓|4|f1|d32|)B|gP|gα_↓|g1|4
1244 α_↓|4|f1|d34|)|4α=↓|4(B|gP|gα_↓|g1|4α+↓|4|f1|d32|))|4α⊗↓|4(b
1244 |gp|4α_↓|4|f1|d32|)); |πhence |ε1|4|¬W|4|≤a|4α=↓|41/(1|4α_↓|
1246 4|f1|d32|)b|gα_↓|gp)|4|¬W|41|4α+↓|4|f1|d32|)B|g1|gα_↓|gP|4α=
1246 ↓|4|≤b. |πThere are integers |εe |πand |εE |πsuch
1254 that log|ε|βB|4|≤a|4|¬W|4e|4|πlog|ε|βB|4b|4α_↓|4E|4|¬W|4|πlo
1255 g|ε|βB|4|≤b, |πsince Weyl's theorem (exercise
1260 3.5<22) implies that there is an integer |εe
1268 |πwith |ε0|4|¬W|4|πlog|ε|βB|4|≤a|4|¬W|4(e|4|πlog|ε|βB)|πmod|
1269 41|4|¬W|4log|ε|βB|4|≤b|4|¬W|41 |πwhen log|ε|βB|4b
1272 |πis irrational. Hence |ε|≤a|4|¬W|4b|ge/B|gE|4|¬W|4|≤b,
1276 |πfor some |εe |πand |εE. |π(Such |εe |πand |εE
1285 |πmay also be found by applying the theory of
1294 continued fractions, see Section 4.5.3.) Now
1300 we have round|ε|βB(b|ge,|4P)|4α=↓|4B|gE, |πand
1304 round|ε|βb(B|gE,|4p)|4|¬W|4b|ge. [CACM |≡1|≡1
1307 (1968), 47<50; |εProc. Amer. Math. Soc. |≡1|≡9
1314 (1968), 716<723.]|'{A3}|π|≡1|≡9|≡.|4|9|εm|β1|4α=↓|4|≤#|¬f|¬o
1316 |¬f|¬o|¬f|¬o|¬f|¬o|≤&|β1|β6, c|β1|4α=↓|41|4α_↓|410/16
1318 |πmakes |εU|4α=↓|4{H11}({H9}(u|β7u|β6)|β1|β0|4.|4.|4.|4(u|β1
1319 u|β0)|β1|β0{H11}){H9}|β2|β5|β6; m|β2|4α=↓|4|≤#|¬f|¬f|¬o|¬o|¬
1320 f|¬f|¬o|¬o|≤&|β1|β6, c|β2|4α=↓|41|4α_↓|410|g2/16|g2
1322 |πmakes |εU|4α=↓|4{H11}({H9}(u|β7u|β6u|β5u|β4)|β1|β0(u|β3u|β
1323 2u|β1u|β0)|β1|β0{H11}){H9}|β6|β5|β5|β3|β6; m|β3|4α=↓|4|≤#|¬f
1324 |¬f|¬f|¬f|¬o|¬o|¬o|¬o|≤&|β1|β6; c|β3|4α=↓|41|4α_↓|410|g4/16|
1325 g4. |π(Cf. exercise 14. This technique is due
1333 to Roy A. Keir, circa 1958.)|'{A24}{H10L12M29}|∨S|∨E|∨C|∨T|∨
1339 I|∨O|∨N|9|∨4|∨.|∨5|∨.|∨1|'{A12}{H9L11M29}|9|1|≡1|≡.|4|9Test
1341 whether or not |εuv|¬S|4|¬W|4u|¬Sv, |πsince the
1347 denominators are positive.|'{A3}|9|1|≡2|≡.|4|9If
1351 |εc|4|¬Q|41 |πdivides both |εu/d |πand |εv/d,
1357 |πthen |εcd |πdivides both |εu |πand |εv.|'{A3}|π|1|9|≡3|≡.|
1364 4|9Let |εp |πbe prime. If |εp|ge |πis a divisor
1373 of |εuv |πand |εu|¬Sv|¬S |πfor |εe|4|¬R|41, |πthen
1380 either |εp|ge|¬Du |πand |εp|ge|¬Dv|¬S |πor |εp|ge|¬Du|¬S
1386 |πand |εp|ge|¬Dv; |πhence |εp|ge|¬D|πgcd(|εu,|4v|¬S)
1390 |πgcd(|εu|¬S,|4v). |πThe converse follows by
1395 reversing the argument.|'{A3}|9|1|≡4|≡.|9|4Let
1399 |εd|β1|4α=↓|4|πgcd(|εu,|4v), d|β2|4α=↓|4|πgcd(|εu|¬S,|4v|¬S)
1400 ; |πthe answer is |εw|4α=↓|4(u/d|β1)(v|¬S/d|β2)
1405 |πsign(|εv), w|¬S|4α=↓|4|¬G(u|¬S/d|β2)(v/d|β1)|¬G,
1407 |πwith a ``divide by zero'' error message if
1415 |εv|4α=↓|40.|'{A3}|1|9|≡5|≡.|4|9d|β1|4α=↓|410,
1417 t|4α=↓|417|4|¬O|47|4α_↓|427|4|¬O|412|4α=↓|4|→α_↓205,
1418 d|β2|4α=↓|45, w|4α=↓|4|→α_↓41, w|¬S|4α=↓|4168.|'
1421 {A3}|π|1|9|≡6|≡.|4|9Let |εu|¬C|4α=↓|4u|¬S/d|β1,
1423 v|¬C|4α=↓|4v|¬S/d|β1; |πwe want to show that
1429 gcd(|εuv|¬C|4α+↓|4u|¬Cv,|4d|β1)|4α=↓|4|πgcd(|εuv|¬C|4α+↓|4u|
1429 ¬Cv, d|β1u|¬Cv|¬C). |πIf |εp |πis a prime which
1437 divides |εu|¬C, |πthen |εp |πdoes not divide
1444 |εu |πor |εv|¬C, |πsp |εp |πdoes not divide |εuv|¬C|4α+↓|4u|
1452 ¬Cv. |πA similar argument holds for prime divisors
1460 of |εv|¬C, |πso no prime divisors of |εu|¬Cv|¬C
1468 |πa=ect the given gcd.|'{A3}|9|1|≡7|≡.|9|4(|εN|4α_↓|41)|g2|4
1472 α+↓|4(N|4α_↓|42)|g2|4α=↓|42N|g2|4α_↓|4(6N|4α_↓|45).
1473 |πIf the inputs are |εn-|πbit binary numbers,
1480 |ε2n|4α+↓|41 |πbits may be necessary to represent
1487 |εt.|'{A3}|9|1|≡8|≡.|4|9|πFor multiplication
1490 and division these quantities will obey the rules
1498 |εx/0|4α=↓|4|πsign(|εx)|¬X, (|¬N|¬X)|4α⊗↓|4x|4α=↓|4x|4α⊗↓|4(
1499 |→|¬N|¬X)|4α=↓|4(|→|¬N|¬X)/x|4α=↓|4|¬N|πsign(|εx)|¬X,
1500 x/(|→|¬N|¬X)|4α=↓|40, |πprovided that |εx |πis
1505 _nite and nonzero, without change to the algorithms
1513 described. Furthermore, the algorithms can readily
1519 be modi_ed so that 0/0|4α=↓|40|4α⊗↓|4(|→|¬N|¬X)|4α=↓|4(|→|¬N
1523 |¬X)|4α⊗↓|40|4α=↓|4``(0/0)'', where the latter
1527 is a representation of ``unde_ned''; and so that
1535 if either operand is ``unde_ned'' the result
1542 will be ``unde_ned'' also. Since the multiplication
1549 and division subroutines can yield these fairly
1556 natural rules of ``extended arithmetic,'' it
1562 is sometimes worth while to modify the addition
1570 and subtraction operations so that they satisfy
1577 the rules |εx|4|¬N|4|¬X|4α=↓|4|→|¬N|¬x, x|4|¬N|4(|→α_↓|¬X)|4
1580 α=↓|4|→|"c|¬x, |πfor |εx |π_nite; (|¬N|¬X)|4α+↓|4(|→|¬N|¬X)|
1584 4α=↓|4|→|¬N|¬X|4α_↓|4(|→|"c|¬X)|4α=↓|4|→|¬N|¬X,
1585 (|→|¬N|¬X)|4α+↓|4(|→|"c|¬X)|4α=↓|4(|→|¬n|¬x)|4α_↓|4(|→|¬N|¬X
1585 )|4α=↓|4(0/0); and if either or both operands
1592 is (0/0), so is the result. Equality tests and
1601 comparisons may be treated in a similar manner.|'
1609 !!|1|1The above remarks are independent of ``over⊗ow''
1616 indications. If |¬X is being used to suggest
1624 over⊗ow, it is incorrect to let 1/|¬x be equal
1633 to zero, or to let |¬X|4α_↓|4|¬X be equal to
1642 zero, lest inaccurate results be regarded as
1649 true answers*3 It is far better to represent over⊗ow
1658 by (0/0), and to use the convention that the
1667 result of any operation is unde_ned if at least
1676 one of the inputs is unde_ned. This type of over⊗ow
1686 indication has the advantage that _nal results
1693 of an extended calculation reveal exactly which
1700 answers are de_ned and which are not.|'{A3}|9|1|≡9|≡.|4|9If
1708 |εu/u|¬S|4|=|↔/α=↓|4v/v|¬S, |πthen|'{A9}|ε1|4|¬E|4|¬Guv|¬S|4
1710 α_↓|4u|¬Sv|¬G|4α=↓|4u|¬Sv|¬S|¬G(u/u|¬S)|4α_↓|4(v/v|¬S)|¬G|4|
1710 ¬W|4|¬G2|g2|gn(u/u|¬S)|4α_↓|42|g2|gn(v/v|¬S)|¬G;|;
1711 {A9}|πtwo quantities di=ering by more than unity
1718 cannot have the same ``⊗oor.'' {H11}({H9}In other
1725 words, the _rst |ε2n |πbits to the right of the
1735 binary point is enough to characterize the value
1743 of the fraction, when there are |εn-|πbit denominators.
1751 We cannot improve this to |ε2n|4α_↓|41 |πbits,
1758 for if |εn|4α=↓|44 |πwe have |f1|d313|)|4α=↓|4(.00010011|4.|
1763 4.|4.)|β2, |f1|d314|)|4α=↓|4(.00010010|4.|4.|4.)|β2.{H11}){H
1764 9}|'{A3}|π|≡1|≡1|≡.|4|9To divide by |ε(v|4α+↓|4v|¬S|¬H|v45|)
1768 )/v|¬C, |πwhen |εv |πand |εv|¬S |πare not both
1776 zero, multiply by{U0}{H10L12M29}58320#Computer
folio 770 galley 4
1779 Programming!(Knuth/A.-W.)!f. 770!ch. 4!g. 4c|'
1783 {A24}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|∨4|∨.|∨5|∨.|∨2|'
1784 {A12}{H9L11M29}|9|1|≡1|≡.|4|9Substitute min,
1786 max, α+↓ consistently for gcd, lcm, α⊗↓.|'{A3}|9|1|≡2|≡.|4|9
1793 For prime |εp, |πlet |εu|βp, v|β1|mp,|4.|4.|4.|4,|4v|βn|βp
1799 |πbe the exponents of |εp |πin the canonical
1807 factorization of |εu, v|β1,|4.|4.|4.|4,|4v|βn.
1811 |πBy hypothesis, |εu|βp|4|¬E|4v|β1|βp|4α+↓|1|1|¬O|4|¬O|4|¬O|
1813 1|1α+↓|4v|βn|βp. |πWe must show that |εu|βp|4|¬E|4|πmin(|εu|
1818 βp,|4v|β1|βp)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4|πmin(|εu|βp,|4v
1818 |βn|βp), |πand this is certainly true if |εu|βp
1826 |πis greater than or equal to each |εv|βj|βp,
1834 |πor if |εu|βp |πis less than some |εv|βj|βp.|'
1842 {A3}|1|9|≡3|≡.|4|9Solution |*/|↔O: |\|πA one-to-one
1846 correspondence is obtained if we set |εu|4α=↓|4|πgcd(|εd,|4n
1852 ), v|4α=↓|4n|g2/|πlcm(|εd,|4n) |πfor each divisor
1857 |εd |πof |εn|g2. Solution |*/|↔P: |\|πIf |εn|4α=↓|4p|ure|)1|g
1863 1|)|4.|4.|4.|4p|ure|)r|gr|), |πthe number in
1867 each case is |ε(2e|β1|4α+↓|41)|4.|4.|4.|4(2e|βr|4α+↓|41).|'
1871 {A3}|π|≡4|≡.|4|9See exercise 3.2.1.2<15(a).|'
1874 {A3}|1|9|≡5|≡.|4|9Shift |εu, v |πright until
1879 neither is a multiple of 3; each iteration sets
1888 |εt|4|¬L|4u|4α+↓|4v |πor |εt|4|¬L|4u|4α_↓|4v
1891 (|πwhichever is a multiple of 3), and shifts
1899 |εt |πright until it is not a multiple of 3,
1909 then replaces max|ε(u,|4v) |πby the result.|'
1915 {A9}|∂|9|1|9|1|9|1|9|1|9|1|∂|9|1|9|1|9|1|9|1|9|1|∂|9|1|9|1|9
1915 |1|9|1|9|1|4|1|4|1|9|1|9|1|9|1|9|1|4|1|4|1|9|1|9|1|9|1|9|1|4
1915 |1|1|∂|E|;|>|εu|;!!!!v|;!!!!t|;>{A3}|>13634|?
1923 !!!!24140|?!!!!10506,|4|13502;|'>|>13636|?!!!!3502|?
1929 !!!!17136,|4|15712,|4|11904;|'>|>1904|?!!!!3502|?
1934 !!!!5406,|4|11802;|'>|>1904|?!!!!1802|?!!!!102,|4|134;|'
1940 >|>34|?!!!!1802|?!!!!1836,|4|1612,|4|1204,|4|168;|'
1945 >|>34|?!!!!68|?!!!!102,|4|134;|'>|>34|?!!!!34|?
1954 !!!!0.|'>{A9}{H9L11M29}|π|1|9|≡6|≡.|4|9The probability
1958 that both |εu |πand |εv |πare even is |f1|d34|);
1967 the probability that both are multiples of four
1975 is |f1|d316|); etc. Thus |εA |πhas the distribution
1983 given by the generating function|'{A9}|f3|d34|)|4α+↓|4|f3|d3
1988 16|)|εz|4α+↓|4|f3|d364|)z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4|
1988 (|f3|d34|)|d21|4α_↓|4z/4|)|4.|;{A9}|πThe mean
1991 is |f1|d33|), and the standard deviation is |¬H|v4|f2|d39|)|
1998 4α+↓|4|f1|d33|)|4α_↓|4|f1|d39|)|4α=↓|4|f2|d33|).
1999 If |εu, v |πare independently and uniformly distributed
2007 with |ε1|4|¬E|4u,|4v|4|¬W|42|gN, |πthen some
2011 small correction terms are needed; the mean is
2019 then actually|'{A9}|ε(2|gN|4α_↓|41)|gα_↓|g2|4|↔k|uc|)1|¬Ek|¬
2021 EN(2|gN|gα_↓|gk|4α_↓|41)|g2|4α=↓|4|f1|d33|)|4α_↓|4|f4|d33|)(
2021 2|gN|4α_↓|41)|gα_↓|g1|4α+↓|4N(2|gN|4α_↓|41)|gα_↓|g2.|;
2022 {A9}|π|9|1|≡7|≡.|4|9When |εu, v |πare not both
2028 even, each of the cases (even, odd), (odd, even),
2037 (odd, odd) is equally probable, and |εB|4α=↓|41,
2044 0, 0 |πin these cases. Hence |εB|4α=↓|4|f1|d33|)
2051 |πon the average. Actually, as in exercise 6,
2059 a small correction could be given to be strictly
2068 accurate when |ε1|4|¬E|4u,|4v|4|¬W|42|gN; |πthe
2072 probability that |εB|4α=↓|41 |πis actually|'{A9}|ε(2|gN|4α_↓
2077 |41)|gα_↓|g2|↔k|uc|)1|¬Ek|¬EN|)(2|gN|gα_↓|gk|4α_↓|41)2|gN|gα
2077 _↓|gk|4α=↓|4|f1|d33|)|4α_↓|4|f1|d33|)(2|gN|4α_↓|41)|gα_↓|g1.
2077 |;{A9}|π|9|1|≡8|≡.|4|9|εE |πis the number of
2083 subtraction cycles in which |εu|4|¬Q|4v, |πplus
2089 one if |εu |πis odd after step B1. If we change
2100 the inputs from |ε(u,|4v) |πto |ε(v,|4u), |πthe
2107 value of |εC |πstays unchanged, while |εE |πbecomes
2115 |εC|4α_↓|4E |πor |εC|4α_↓|4E|4α_↓|41; |πthe latter
2120 case occurs i= |εu |πand |εv |πare both odd after
2130 step B1, and this has probability |f1|d33|)|4α+↓|4|f2|d33|)/
2136 (2|ε|gN|4α_↓|41). |πHence|'{A9}|εE|π|βa|βv|βe|4α=↓|4|εC|π|βa
2138 |βv|βe|4α_↓|4|εE|π|βa|βv|βe|4α_↓|4|f1|d33|)|4α_↓|4|f2|d33|)/
2138 (2|ε|gN|4α_↓|41).|;{A9}|π|1|9|≡9|≡.|4|9The binary
2141 algorithm _rst gets to B6 with |εu|4α=↓|41963,
2148 v|4α=↓|41359; |πthen |εt|4|¬L|4604, 302, 151,
2153 |πetc. The gcd is 302. Using Alforithm X we _nd
2163 that 2|4|¬O|431408|4α_↓|423|4|¬O|42718|4α=↓|4302.|'
2165 {A3}|≡1|≡0|≡.|4|9(a) Two integers are relatively
2170 prime i= they are not both divisible by any prime
2180 number. (b) Rearrangement of the sum in (a),
2188 in terms of the denominators |εk|4α=↓|4p|β1|4.|4.|4.|4p|βr.
2194 (|πNote that each of the sums in (a), (b) is
2204 actually _nite.{H11}){H9} (c) |ε(n/k)|g2|4α_↓|4|"ln/k|"L|g2|
2207 4α=↓|4O(n/k), |πso |εq|βn|4α_↓|4|¬K|ur|)1|¬Ek|¬En|)|4|≤m(k)(
2209 n/k)|g2|4α=↓|4|¬K|ur|)1|¬Ek|¬En|)|4O(n/k)|4α=↓|4O(nH|βn).
2210 (|πd) |¬K|ur|)|εd|¬Dn|)|4|≤m(d)|4α=↓|4|≤d|β1|βn.
2212 |π[In fact we have the more general result|'{A9}|ε|↔k|uc|)d|
2220 ¬Dn|)|4|≤m(d)|↔a|(n|d2d|)|↔s|gs|4α=↓|4n|gs|4α_↓|4|↔k|4|↔a|(n
2220 |d2p|)|↔s|gs|4α+↓|1|1|¬O|4|¬O|4|¬O|4,|;{A9}|πas
2222 in part (b), where the sums are over the prime
2232 divisors of |εn, |πand this equals |εn|gs(1|4α_↓|41/p|urs|)1
2238 |))|4.|4.|4.|4(1|4α_↓|41/p|urs|)r|)) |πif |εn|4α=↓|4p|ure|β1
2240 |)1|)|4.|4.|4.|4p|ure|βr|)r|).]|'!!|1|1Notes|*/:
2242 |\|πThis proof of Theorem D is due to F. Mertens.
2252 |εJ. f|=4ur die reine und angew. Math. |≡7|≡7
2260 (1874), 289<291. |πThe technique gives a much
2267 stronger result, namely that |ε6|≤p|gα_↓|g2n|g2|4α+↓|4O(n|4|
2271 πlog|4|εn) |πpairs of integers |εu|¬A{H11}({H9}f(n),
2276 f(n)|4α+↓|4n{H11}){H9}, v|4|¬A|4{H11}[{H9}g(n),
2278 g(n)|4α+↓|4n{H11}) {H9}|πare relatively prime,
2282 for arbitrary |εf |πand |εg. |πSimilarly, a set
2290 of |εk |πintegers is relatively prime with probability
2298 |ε1/(|¬K|ur|)n|¬R1|)|41/n|gk).|'{A3}|π|≡1|≡1|≡.|4|9(a)
2300 6/|ε|≤p|g2 |πtimes 1|4α+↓|4|f1|d34|)|4α+↓|4|f1|d39|),
2303 namely 49/6|ε|≤p|g2|4|¬V|4.82746. |π(b) 6/|ε|≤p|g2
2307 |πtimes 1/1|4α+↓|42/4|4α+↓|43/9|4α+↓|1|1|¬O|4|¬O|4|¬O|4,
2309 namely |¬X*3 {H11}({H9}This is true in spite of
2317 the result of exercise 12, and in spite of the
2327 fact that the average value of ln gcd(|εu,|4v)
2335 |πis a small, _nite number.{H11})|'{A3}{H9L11M29}|≡1|≡2|≡.|4
2340 |9Let |ε|≤s(n) |πbe the number of positive divisors
2348 of |εn. |πThe answer is|'{A9}|ε|↔k|uc|)k|¬R1|)|4|≤s(k)|4|¬O|
2353 4|(6|d2|≤p|g2k|g2|)|4α=↓|4|(6|d2|≤p|g2|)|4{H12}|↔a{H9}|↔k|uc
2353 |)k|¬R1|)|4|(1|d2k|g2|){H12}|↔s{H9}|g2|4α=↓|4|(|≤p|g2|d26|)|
2353 4.|;{A9}|π[Thus, the average is |εless |πthan
2360 2, although there are always at least two common
2369 divisors when |εu, v |πare not relatively prime.]|'
2377 {A3}|≡1|≡3|≡.|4|91|4α+↓|4|f1|d39|)|4α+↓|4|f1|d325|)|4α+↓|1|1
2377 |¬O|4|¬O|4|¬O|1|1α=↓|41|4α+↓|4|f1|d34|)|4α+↓|4|f1|d39|)|4α+↓
2377 |1|1|¬O|4|¬O|4|¬O|1|1α_↓|4|f1|d34|)(1|4α+↓|4|f1|d34|)|4α+↓|4
2377 |f1|d39|)|4α+↓|1|1|¬O|4|≡O|4|≡O).|'{A3}|≡1|≡4|≡.|4|9|εv|β1|4
2378 α=↓|4|→|"cv/u|β3,|4v|β2|4α=↓M7O0|"cu/u|β3 |π(the
2380 sign depends on whether the number of iterations
2388 is even or odd). This follows from the fact that
2398 |εv|β1 |πand |εv|β2 |πare relatively prime to
2405 each other (throughout the algorithm), and that
2412 |εv|β1u|4α=↓|4|→α_↓v|β2v. |π[Hence |εv|β1u|4α=↓|4|πlcm(|εu,|
2414 4v) |πat the close of the alforithm, but this
2423 is not an especially e∃cient way to compute the
2432 least common multiple. For a generalization,
2438 see exercise 4.6.1<18.]|'!!|1|1G. E. Collins
2444 has observed that |ε|¬Gu|¬G|4|¬E|4|f1|d32|)v/u|β3,
2448 |¬Gu|β2|¬G|4|¬E|4|f1|d32|)u/u|β3, |πat the termination
2452 of Algorithm X, except in certain trivial cases,
2460 since the _nal value of |εq |πis usually |→|¬R2.
2469 This bounds the size of |ε|¬Gu|β1|¬G, |¬Gu|β2|¬G
2476 |πthroughout the execution of the alforithm.|'
2482 {A3}|≡1|≡5|≡.|4|9Apply Algorithm X to |εv |πand
2488 |εm, |πthus obtaining a value |εx |πsuch that
2496 |εxv|4|"o|41 |π(modulo |εm). |π(This can be done
2503 by simplifying Algorithm X so that |εu|β2 |πand
2511 |εv|β2 |πare not computed, since they are never
2519 used in the answer.) Then set |εw|4|¬L|4ux |πmod
2527 |εm. |π[It follows, as in exercise 30, that this
2536 process requires |εO(n|g2) |πunits of time, when
2543 it is applied to large |εn-|πbit numbers.]|'|H*?*?{U0}{H9L11M2
folio 772 galley 5
2550 9}58320#Computer Programming!(Knuth/A.-W.)!F.
2552 772!ch. 4!g. 5c|'{A12}|π|≡1|≡6|≡.|4|9(a) Set
2557 |εt|β1|4α=↓|4x|4α+↓|42y|4α+↓|43z; |πthen |ε3t|β1|4α+↓|4y|4α+
2559 ↓|42z|4α=↓|41, 5t|β1|4α_↓|43y|4α_↓|420z|4α=↓|43.
2561 |πEliminate |εy, |πthen |ε14t|β1|4α_↓|414z|4α=↓|46:
2565 |πNo solution. (b) This time |ε14t|β1|4α_↓|414z|4α=↓|40.
2571 |πDivide by 14, eliminate |εt|β1; |πthe general
2578 solution is |εx|4α=↓|48z|4α_↓|42, y|4α=↓|41|4α_↓|45z,
2582 z |πarbitrary.|'{A3}|≡1|≡7|≡.|9|4Let |εu|β1,
2586 u|β2, u|β3, v|β1, v|β2, v|β3 |πbe multiprecision
2593 variables, not just |εu |πand |εv. |πThe extended
2601 algorithm will act the same on |εu|β3 |πand |εv|β3
2610 |πas Algorithm L does on |εu |πand |εv. |πNew
2619 multiprecision operations are to set |εt|4|¬L
2625 Au|βj, t|4|¬L|4t|4α+↓|4Bv|βj, w|4|¬L|4Cu|βj,
2628 w|4|¬L|4w|4α+↓|4Dv|βj, u|βj|4|¬L|4t, v|βj|4|¬L|4w
2631 |πfor all |εj, |πin step L4; also if |εB|4α=↓|40
2640 |πin that step to set |εt|4|¬L|4u|βj|4α_↓|4qv|βj,
2646 u|βj|4|¬L|4v|βj, v|βj|4|¬L|4t |πfor all |εj |πand
2652 for |εq|4α=↓|4|"lu|β3/v|β3|"L. |πA similar modi_cation
2657 is made to step L1 if |εv|β3 |πis small. The
2667 inner loop (steps L2 and L3) is unchanged.|'{A3}|≡1|≡8|≡.|4|
2675 9If |εmn|4α=↓|40, |πthe probabilities of the
2681 lattice-point model in the test are exact, so
2689 we may assume that |εm|4|¬R|4n|4|¬Q|40. |εValida
2695 vi, |πthe following values have been obtained:|'
2702 {A3}!!|1|1|εCase |*/|↔O|\, m|4α=↓|4n. |πFrom (|εn,|4n)
2707 |πwe go to |ε(n|4α_↓|4t,|4n) |πwith probability
2713 |εt/2|gt|4α_↓|45/2|gt|gα+↓|g1|4α+↓|43/2|g2|gt,
2714 |πfor |ε2|4|¬E|4t|4|¬W|4n. (|πThese values are
2719 |f1|d316|), |f7|d364|), |f27|d3256|),|4.|4.|4.|4.)
2722 |πTo (0,|4|εn) |πthe probability is |εn/2|gn|gα_↓|g1|4α_↓|41
2727 /2|gn|4α+↓|41/2|g2|gn|gα_↓|g2. |πTo (|εn,|4k)
2730 |πthe probability is the same as to |ε(k,|4n).
2738 |πThe algorithm terminates with probability |ε1/2|gn|gα_↓|g1
2743 .|'{A3}!!|1|1Case |*/|↔P|\, m|4α=↓|4n|4α+↓|41.
2747 |πFrom (|εn|4α+↓|41, n) |πwe get to |ε(n,|4n)
2754 |πwith probability |f1|d38|) when |εn|4|¬Q|41,
2759 |πor 0 when |εn|4α=↓|41; |πto |ε(n|4α_↓|4t, n)
2766 |πwith probability 11/2|ε|gt|gα+↓|g3|4α_↓|43/2|g2|gt|gα+↓|g1
2768 , |πfor |ε1|4|¬E|4t|4|¬W|4n|4α_↓|41. (|πThese
2772 values are |f5|d316|), |f1|d34|),|4.|4.|4.|4.)
2776 We get to (1,|4|εn) |πwith probability |ε5/2|gn|gα+↓|g1|4α_↓
2782 |43/2|g2|gn|gα_↓|g1, |πfor |εn|4|¬Q|41; |πto
2786 (0,|4|εn) |πwith probability 3/2|gn|4α_↓|41/2|g2|g|εn|4α_↓|4
2789 1/2|g2|gn|gα_↓|g1.|'!!|1|1Case |*/|↔L|\, m|4|¬R|4n|4α+↓|42.
2793 |πThe probabilities are given by the following
2800 table:|'{A6}|h|ε|∂(m|4α_↓|4n|4α_↓|41,|4n):|9|∂1/2|gt|4α+↓|43
2801 /2|gm|gα_↓|gn|gα+↓|gt|gα+↓|g1,|91|4|¬W|4t|4|¬W|4n;|E|n|;
2802 |L(m|4α_↓|41,|4n):|L1/2|4α_↓|43/2|gm|gα_↓|gn|gα+↓|g2|4α_↓|4|
2802 ≤d|βn|β1/2|gm|gα+↓|g1;>|L(m|4α_↓|4t,|4n):|L1/2|gt|4α+↓|43/2|
2803 gm|gα_↓|gn|gα+↓|gt|gα+↓|g1,|91|4|¬W|4t|4|¬W|4n;>
2804 |L(m|4α_↓|4n,|4n):|L1/2|gn|4α+↓|41/2|gm,|9n|4|¬Q|41;>
2805 |L(m|4α_↓|4n|4α_↓|41,|4n):|L1/2|gn|gα+↓|g1|4α+↓|41/2|gm|gα_↓
2805 |g1;>|L(m|4α_↓|4n|4α_↓|4t,|4n):|L1/2|gn|gα+↓|gt,|91|4|¬W|4t|
2806 4|¬W|4m|4α_↓|4n;>|L(0,|4n):|L1/2|gm|gα_↓|g1.>
2808 {A6}!!|1|1[Note|*/: |\|πAlthough these exact probabilities
2813 will certainly improve on the lattice-point model
2820 considered in the text, they lead to recurrence
2828 relations of much greater complexity; and they
2835 will not provide the true behavior of Algorithm
2843 B, since for example the probability that gcd(|εu,|4v)|4α=↓|
2850 45 |πis di=erent from the probability that gcd(|εu,|4v)|4α=↓
2857 |47.]|'{A3}|h|εA|βn|βα+↓|β1|4|∂α=↓|4a|4α+↓|4|↔k|42|gα_↓|gkA|
2858 βn|β(|βn|βα_↓|βk|β)|4α+↓|42|4(1|4α_↓|42|gα_↓|gn)|4α+↓|42|gα_
2858 ↓|gnb|E|n|;|≡1|≡9|≡.|E|'| A|βn|βα+↓|β1|4|Lα=↓|4a|4α+↓|4|↔k|u
2860 c|)1|¬Ek|¬En|)|42|gα_↓|gkA|ur|)(nα+↓1)(nα_↓k)|)|4α+↓|42|gα_↓
2860 |gnb>{A4}|Lα=↓|4a|4α+↓|4|↔k|uc|)1|¬Ek|¬En|)|42|gα_↓|gkA|ur|)
2861 n(nα_↓k)|)|4α+↓|4|(c|d22|)|4(1|4α_↓|42|gα_↓|gn)|4α+↓|42|gα_↓
2861 |gnb>{A4}|Lα=↓|4a|4α+↓|4|f1|d32|)A|ur|)n(nα_↓1)|)|4α+↓|4|f1|
2862 d32|)(A|βn|4α_↓|4a)|4α+↓|4|(c|d22|)|4(1|4α_↓|42|gα_↓|gn);>
2863 {A6}|πnow substitute for |εA|βn|β(|βn|βα_↓|β1|β)
2867 |πfrom (36).|'{A3}|≡2|≡0|≡.|4|9The paths described
2872 in the hint have the same probability, only the
2881 subsequent termination of the alforithm has a
2888 di=erent probability; thus |ε|≤l|4α=↓|4k|4α+↓|41
2892 |πwith probability 2|gα_↓|ε|gk |πtimes the probability
2898 that |ε|≤l|4α=↓|41. |πLet the latter probability
2904 be |εp. |πWe know from the text that |ε|≤l|4α=↓|40
2913 |πwith approximate probability |f3|d35|); hence
2918 |f2|d35|)|4α=↓|4|εp(1|4α+↓|4|f1|d32|)|4α+↓|4|f1|d34|)|4α+↓|4
2918 |f1|d38|)|4α+↓|1|1|¬O|4|¬O|4|¬O)|4α=↓|42p. |πThe
2920 average is |εp(1|4α+↓|4|f2|d32|)|4α+↓|4|f3|d34|)|4α+↓|4|f4|d
2922 38|)|4α+↓|1|1|¬O|4|¬O|4|¬O)|4α=↓|4p(1|4α+↓|4|f1|d32|)|4α+↓|4
2922 |f1|d34|)|4α+↓|4|f1|d38|)|4α+↓|1|1|¬O|4|¬O|4|¬O)|g2|4α=↓|44p
2922 . |π[The exact probability that |ε|≤l|4α=↓|41
2928 |πis |f1|d35|)|4α_↓|4|f6|d35|)(|→α_↓|f1|d34|))|ε|gn
2930 |πif |εm|4|¬Q|4n|4|¬R|41, |f1|d35|)|4α_↓|4|f16|d35|)(|→α_↓|f
2932 1|d34|))|gn |πif |εm|4α=↓|4n|4|¬R|42.]|'{A3}|π|≡2|≡1|≡.|4Sho
2935 w that for _xed |εv |πand for |ε2|gm|4|¬W|4u|4|¬W|42|gm|gα+↓
2942 |g1, |πwhen |εm |πis large, each subtraction-shift
2949 cycle of the algorithm reduces |"llg|β2|4|εu|"L
2955 |πby two on the average.|'{A3}|≡2|≡2|≡.|4|9Exactly
2961 |ε(N|4α_↓|4m)2|gm|gα_↓|g1|gα+↓|g|≤d|rm|r0 |πintegers
2963 |εu |πin the range |ε1|4|¬E|4u|42|gN |πhave |"llg|β2|4|εu|"L
2969 |4α=↓|4m |πafter |εu |πhas been shifted right
2976 until it is odd.|'{A3}|≡2|≡3|≡.|4|9The _rst sum
2983 is |ε2|g2|gN|gα_↓|g2 |¬K|ur|)0|¬Em|¬Wn|¬WN|)|4mn2|gα_↓|gm|gα
2985 _↓|gn{H11}({H9}(|≤a|4α+↓|4|≤b)N|4α+↓|4|≤g|4α_↓|4|≤am|4α_↓|4|
2985 ≤bn{H11}){H9}. |πSince |ε|¬K|ur|)0|¬Em|¬Wn|)|4m2|gα_↓|gm|gα=
2987 ↓|g2|4α_↓|4(nα+↓|41)2|g1|gα_↓|gn |πand |ε|¬K|ur|)0|¬Em|¬Wn|)
2989 m(m|4α_↓|41)2|gα_↓|gm|4α=↓|44|4α_↓|4(n|g2|4α+↓|4n|4α+↓|42)2
2990 |g1|gα_↓|gn, |πthe sum on |εm |πis |ε2|g2|gN|gα_↓|g2|4|¬K|ur
2996 |)0|¬En|¬WN|)|4n2|gα_↓|gn{H11}({H9}(|≤g|4α_↓|4|≤a|4α+↓|4(|≤a
2996 |4α+↓|4|≤b)N)(2|4α_↓|4(n|4α+↓|41)2|g1|gα_↓|gn|4α_↓|4|≤a(4|4α
2996 _↓|4(n|g2|4α+↓|4n|4α+↓|42)2|g1|gα_↓|gn)|4α_↓|4|≤bn{H11}){H9}
2996 |4α=↓|42|g2|gN|gα_↓|g2{H11}({H9}(|≤a|4α+↓|4|≤b)N|4|¬K|ur|)0|
2996 ¬En|¬WN|)|4n2|gα_↓|gn(2|4α_↓|4(n|4α+↓|41)2|g1|gα_↓|gn)|4α+↓|
2996 4O(1){H11}){H9}. |πThus the coe∃cient of |ε(|≤a|4α+↓|4|≤b)N
3002 |πin the answer is found to be 2|gα_↓|g2{H11}({H9}4|4α_↓|4(|
3009 f4|d33|))|g3{H11}){H9}|4α=↓|4|f11|d327|). A similar
3012 argument applies to the other sum.|'!!|1|1[|εNote|*/:
3019 |\|πThe |εexact |πvalue of the sums ay be obtained
3029 after some tedious calculation by means of the
3037 general formula|'{A6}|ε|↔k|uc|)0|¬Ek|¬Wn|)k|gmz|gk|4α=↓|4|(m
3039 *3z|gm|d2(1|4α_↓|4z)|gm|gα+↓|g1|)|4α_↓|4|↔k|uc|)0|¬Ek|¬Em|)|4
3039 |(m|gkn|gm|gα_↓|gkz|gn|gα+↓|gk|d2(1|4α_↓|4z)|gk|gα+↓|g1|)|;
3040 {A6}|πwhich follows from summation by parts.]|'
3046 |≡2|≡4|≡.|4|9Solving a recurrence similar to
3051 (34), we _nd that the number of times is |εA|βm|βn,
3061 |πwhere |εA|β0|β0|4α=↓|41, A|β0|βn|4α=↓|4(n|4α+↓|43)/2,
3064 A|βn|βn|4α=↓|4|f8|d35|)|4α_↓|4(3n|4α+↓|413)/(9|4|¬O|42|gn)|4
3064 α+↓|4|f128|d345|)(|→α_↓|f1|d34|))|gn |πif |εn|4|¬R|41,
3067 A|βm|βn|4α=↓|4|f16|d315|)(|→α_↓|f1|d34|))|gn
3068 |πif |εm|4|¬Q|4n|4|¬R|41. |πSince the condition
3073 |εu|4α=↓|41 |πor |εv|4α=↓|41 |πis therefore satis_ed
3079 only about 1.6 times in an average run, it is
3089 not worth making the suggested test each time
3097 step B5 is performed. (Of course the lattice
3105 model is not completely accurate, but it seems
3113 reasonable to believe that it is not too inaccurate
3122 for this application.)|'{A3}|≡2|≡5|≡.|4|9(a)
3126 |εF|βn|βα+↓|β1(x)|4α=↓|4|¬K|ur|)d|¬R1|)2|gα_↓|gd|4|πPr(|εX|β
3126 n|4|¬W|41 |πand |ε2|gd/(X|urα_↓1|)n|)|4α_↓|41)|4|¬W|4x
3129 |πor |εX|βn|4|¬Q|41 |πand (|εX|βn|4α_↓|41)/2|gd|4|¬W|4x{H11}
3132 ){H9}|4α=↓|4|¬K|βd|β|¬R|β1|42|gα_↓|gd{H11}({H9}F|βn(1/(1|4α+
3132 ↓|42|gdx|gα_↓|g1){H11}){H9}|4α+↓|4F|βn(1|4α+↓|42|gdx)|4α_↓|4
3132 F|βn(1){H11}){H9}. |π(b) |εG|βn|βα+↓|β1(x)|4α=↓|41|4α_↓|4|¬K
3134 |βd|β|¬R|β12|gα_↓|gd{H11}({H9}G|βn(1/(1|4α+↓|42|gdx))|4α_↓|4
3134 G|βn(1/(1|4α+↓|42|gdx|gα_↓|g1)){H11}){H9}. (|πc)
3136 |εH|βn(x)|4α=↓|4|¬K|βd|β|¬R|β12|gα_↓|gd|4|πPr{H11}({H9}Y|βn|
3136 4|¬E|4x and |ε(1|4α_↓|4Y|βn)/2|gd|4|¬E|4x{H11}){H9}|4α=↓|4|¬
3138 K|βd|β|¬R|β1|42|gα_↓|gd|4|πmax{H11}({H9}0,|4|εG|βn(x)|4α_↓|4
3138 G|βn(1|4α_↓|42|gdx){H11}){H9}.|'!!|1|1|πStarting
3140 with |εG|β0(x)|4α=↓|4x |πwe get rapid convergences
3146 to a limiting distribution where {H11}({H9}G(.1),|4.|4.|4.|4
3151 ,|4|εG(.9){H11}){H9}|4α=↓|4(.2750, .4346, .5544,
3154 .6507, .7310, .7995, .8590, .9114, .9581). |πThe
3161 expected value of ln max(|εu|βn|m1v|βn)/|πmax(|εu|βn|βα+↓|β1
3165 , v|βn|βα+↓|β1) |πis |¬J|ur1|)0|)|ε|4H|βn(t)|4dt/t,
3169 |πand Brent has shown that this can be written|'
3178 {A6}{A6}|↔j|ur1|)1/3|)|4|(|εG|βn(t)|d2t|)|4dt|4α_↓|4|↔j|ur1/
3178 3|)0|)|4|(G|βn(t)|d21|4α_↓|4t|)|4dt|4α+↓|4|↔k|uc|)k|¬R1|)|42
3178 |gα_↓|gk|ur1/(1α+↓2|gk)|)1/(1α+↓2|gk|gα+↓|g1)|)|4|(G|βn(t)|d
3178 2t(1|4α_↓|4t)|)|4dt.|;{A6}{H9L11M29}|π|≡2|≡6|≡.|4|9By
3180 induction, the length is |εm|4α+↓|4|"ln/2|"L
3185 |πwhen |εm|4|¬R|4n, |πexcept that when |εm|4α=↓|4n|4α=↓|41
3191 |πthere is |εno |πpath to (0,|40).|'|Hβ*?*?*?{U0}{H9L11M29}5832
folio 776 galley 6
3197 0#Computer Programming!(Knuth/A.-W.)!ch. 4!f.
3200 776!g. 6c|'{A12}|≡2|≡7|≡.|4|9Let |εa|βn|4α=↓|4{H11}({H9}2|gn
3203 |4α_↓|4(|→α_↓1)|gn{H11}){H9}/3; |πthen |εa|β0,
3206 a|β1, a|β2,|4.|4.|4.|4α=↓|40, 1, 1, 3, 5, 11,
3213 21,|4.|4.|4. (|πThis sequence of numbers has
3219 an interesting pattern of zeros and ones in its
3228 binary representation. Note that |εa|βn|4α=↓|4a|βn|βα_↓|β1|4
3232 α+↓|42a|βn|βα_↓|β2, |πand |εa|βn|4α+↓|4a|βn|βα+↓|β1|4α=↓|42|
3234 gn..) |πFor |εm|4|¬Q|4n, |πlet |εu|4α=↓|42|gm|gα+↓|g1|4α_↓|4
3238 a|βn|βα+↓|β2, v|4α=↓|4a|βn|βα+↓|β2. |πFor |εm|4α=↓|4n|4|¬Q|4
3241 0, |πlet |εu|4α=↓|4a|βn|βα+↓|β2, v|4α=↓|42a|βn|βα+↓|β1,
3245 |πor |εu|4α=↓|42a|βn|βα+↓|β1, v|4α=↓|4a|βn|βα+↓|β2
3248 (|πdepending on which is larger). Another example
3255 for |εm|4α=↓|4n|4|¬Q|40 |πis |εu|4α=↓|42|gn|gα+↓|g1|4α_↓|41,
3258 v|4α=↓|42|gn|gα+↓|g1|4α_↓|42; |πthis takes more
3263 shifts, and gives |εC|4α=↓|4n|4α+↓|41, D|4α=↓|42n,
3268 E|4α=↓|41.|'{A3}|π|≡2|≡8|≡.|4|9This is a problem
3273 where it appears to be necessary to prove |εmore
3282 |πthan was asked just to prove what was asked.
3291 Let us prove the following: |εIf u, v are positive
3301 integers, Algorithm B takes |¬E1|4α+↓|4|"l|πlg|β2|4max(|εu,|
3305 4v)|"L |εsubtraction cycles|*/; |\and if equality
3311 holds, then |"l|πlg|β2|4(|εu|4α+↓|4v)|"L|4|¬Q|4|"l|πlg|β2|4m
3313 ax(|εu,|4v)|"L.|'|π!!|1|1For convenience, let
3317 us assume that |εu|4|¬R|4v; |πlet |εm|4α=↓|4|"l|πlg|β2|4|εu|
3322 "L, n|4α=↓|4|"l|πlg|β2|4|εv|"L; |πand let us
3327 use the ``lattice-point'' terminology, saying
3332 that we are ``at point |ε(m,|4n).'' |πThe proof
3340 is by induction on |εm|4α+↓|4n.|'!!|1|1Case |*/|↔O|\,
3347 m|4α=↓|4n. |πClearly, |"llg|β2(|εu|4α+↓|4v)|"L|4|¬Q|4|"l|πlg
3349 |β2|4|εu|"L |πin this case. If |εu|4α=↓|4v |πthe
3356 result is trivial; otherwise the next subtraction-shift
3363 cycle takes us to a point |ε(m|4α_↓|4k,|4m).
3370 |πBy induction, at most |εm|4α+↓|41 |πfurther
3376 subtraction steps will be required; but if |εm|4α+↓|41
3384 |πmore |εare |πneeded, we have |"llg|β2{H11}({H9}(|εu|4α_↓|4
3389 v)2|gα_↓|gr|4α+↓|4v{H11}){H9}|"L|4|¬Q|4|"l|πlg|β2|4|εv|"L,
3390 |πwhere |εr|4|¬R|41 |πis the number of right
3397 shifts that were made. This is impossible, since
3405 |ε(u|4α_↓|4v)2|gα_↓|gr|4α+↓|4v|4|¬W|4(u|4α_↓|4v)|4α+↓|4v|4α=
3405 ↓|4u, |πso at most |εm |πfurther steps are needed.|'
3414 !!|1|1|εCase |*/|↔P|\, m|4|¬Q|4n. |πThe next subtraction
3420 step takes us to |ε(m|4α_↓|4k,|4n), |πand at
3427 most 1|4α+↓|4max(|εm|4α_↓|4k,|4n)|4|¬E|4m |πfurther
3430 steps will be required. Now if |εm |πfurther
3438 steps |εare |πrequired, then |εu |πhas been replaced
3446 by |εu|¬S|4α=↓|4(u|4α_↓|4v)2|gα_↓|gr |πfor some
3450 |εr|4|¬R|41. |πBy induction, |"llg|β2(|εu|¬S|4α+↓|4v)|"L|4|¬
3453 R|4m; |πhence|'{A9}|"llg|β2(|εu|4α+↓|4v)|"L|4α=↓|4|"l|πlg|β2
3455 |42{H11}({H9}(|εu|4α_↓|4v)/2|4α+↓|4v{H11}){H9}|"L|4|¬R|4|"l|
3455 πlg|β2|42(|εu|¬S|4α+↓|4v)|"L|4|¬R|4m|4α+↓|41|4|¬Q|4|"l|πlg|β
3455 2|4|εu|"L.|;{A9}|π|≡2|≡9|≡.|4|9Subtract the |εk|πth
3459 column from the |ε2k|πth, |ε3k|πth, |ε4k|πth,
3465 etc., for |εk|4α=↓|41, 2, 3,|4.|4.|4.|4. |πThe
3471 result is a triangular matrix with |εx|βk |πon
3479 the diagonal in column |εk, |πwhere |εm|4α=↓|4|¬K|ur|)d|¬Dm|
3485 )|4x|βd. |πIt follows that |εx|βm|4α=↓|4|≤'(m),
3490 |πso the determinant is |ε|≤'(1)|≤'(2)|4.|4.|4.|4|≤'(n).
3495 [|πIn general, ``Smith's determinant,'' in which
3501 the |ε(i,|4j) |πelement is |εf|1{H11}({H9}|πgcd(|εi,|4j){H11
3505 }){H9} |πfor an arbitrary function |εf, |πis
3512 equal to |≥7|ur|)|ε1|¬Em|¬En|)|4|¬K|ur|)d|¬Dm|)|4|≤m(m/d)f(d
3514 ), |πby the same argument. See L. E. Dickson,
3523 |εHistory of the Theory of Numbers |≡1 |π(New
3531 York: Chelsea, 1952), 122<123.]|'{A3}|≡3|≡0|≡.|4|9To
3536 determine |εA |πand |εr |πsuch that |εu|4α=↓|4Av|4α+↓|4r,
3543 0|4|¬E|4r|4|¬W|4v, |πusing ordinary long division,
3548 takes |εO{H11}({H9}(1|4α+↓|4|πlog|4|εA)(|πlog|4|εu){H11}){H9
3549 } |πunits of time. If the quotients during the
3558 algorithm are |εA|β1, A|β2,|4.|4.|4.|4, A|βm,
3563 |πthen |εA|β1A|β2|4.|4.|4.|4A|βm|4|¬E|4u, |πso
3566 log |εA|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4|πlog|4|εA|βm|4|¬E|
3567 4|πlog|4|εu. |πAlso |εm|4α=↓|4O(|πlog|4|εu).|'
3570 {A3}|π|≡3|≡1|≡.|4|9Since |ε(a|gu|4α_↓|41)|4|πmod|4(|εa|gv|4α
3571 _↓|41)|4α=↓|4a|gu|4|π|gm|go|gd|4|ε|gv|4α_↓|41
3572 (|πcf. Eq. 4.3.2<19), we _nd that gcd(|εa|gm|4α_↓|41,
3579 a|gn|4α_↓|41)|4α=↓|4a|ur|πgcd(|εm,n)|)|)|4α_↓|41
3580 |πfor all positive integers |εa.|'{A3}{H9L11M29}|π|≡3|≡2|≡.|
3585 4|9Yes, to |εO{H11}({H9}n(|πlog|4|εn)|g2(|πlog|4log|4|εn){H1
3587 1}){H9}; |πsee A. Sch|=4onhage, |εActa Informatica
3593 |≡1 (1971), |π139<144. [But Algorithm L is better
3601 in practice unless |εn |πis extremely large.]|'
3608 {A3}|≡3|≡4|≡.|4|9Keep track of the most signi_cant
3614 and least signi_cant words of the operands (the
3622 most signi_cant is used to guess the sign of
3631 |εt |πand the least signi_cant is to determine
3639 the amount of right shift), while building a
3647 2|4α⊗↓|42 matrix of single-precision integers
3652 |εA |πsuch that |εA(|fu|d5v|))|4α=↓|4(|fu|¬Sw|d5v|¬Sw|))
3656 |πwhere |εu|¬S |πand |εv|¬S |πare smaller than
3663 |εu |πand |εv. (|πInstead of dividing the simulated
3671 odd operand by 2, multiply the other one by 2,
3681 until obtaining multiples of the word size |εw
3689 |πafter exactly lg |εw |πshifts.) Experiments
3695 show this algorithm running four times as fast
3703 as Algorithm L.|'{A3}{A24}{H10L12M29}|∨S|∨E|∨C|∨T|∨I|∨O|∨N
3707 |∨4|∨.|∨5|∨.|∨3|'{A12}{H9L11M29}|1|9|≡1|≡.|4|9The
3709 running time is about 19.02|εT|4α+↓|46, |πjust
3715 a tri⊗e slower than Program 4.5.2A.|'{A3}|1|9|≡2|≡.|9|4|↔a|(
3721 |εQ|βn(x|β1,|4.|4.|4.|4,|4x|βn)|d2Q|βn|βα_↓|β1(x|β2,|4.|4.|4
3721 .|4,|4x|βn)|)!|(Q|βn|βα_↓|β1(x|β1,|4.|4.|4.|4,|4x|βn|βα_↓|β1
3721 )|d5Q|βn|βα_↓|β2(x|β2,|4.|4.|4.|4,|4x|βn|βα_↓|β1)|)|↔s.|'
3722 {A3}|1|9|≡3|≡.|4|9Q|βn(x|β1,|4.|4.|4.|4,|4x|βn).|'
3723 {A3}|1|9|≡4|≡.|4|9|πBy induction, or by taking
3728 the determinant of the matrix product in exercise
3736 2.|'{A3}|1|9|≡5|≡.|4|9When the |εx'|πs are positive,
3742 the |εq'|πs of (9) are positive, and |εq|βn|βα+↓|β1|4|¬Q|4q|
3749 βn|βα_↓|β1; |πhence (9) is an alternating series
3756 of decreasing terms, and it converges if and
3764 only if |εq|βn|4|¬M|4|¬X. |πBy induction, if
3770 the |εx'|πs are greater than |ε|≤e, q|βn|4|¬R|4c(1|4α+↓|4|≤e
3776 /2)|gn, |πwhere |εc |πis chosen such that |ε1|4|¬R|4c,
3784 |≤e|4|¬R|4c(1|4α+↓|4|≤e/2). |πBut if |εx|βn|4α=↓|41/2|gn
3788 |πthen |εq|βn|4|¬E|42|4α_↓|41/2|gn.|'{A3}|1|9|≡6|≡.|4|9|πIt
3791 su∃ces to prove that |εA|β1|4α=↓|4B|β1; |πand
3797 from the fact that |ε0|4|¬E|4|"Cx|β1,|4.|4.|4.|4,|4x|βn|"C|4
3801 |¬W|41 |πwhenever |εx|β1,|4.|4.|4.|4,|4x|βn |πare
3805 positive integers, we have |εB|β1|4α=↓|4|"l1/X|"L|4α=↓|4A|β1
3809 .|'{A3}|π|1|9|≡7|≡.|4|9Only 1|42|4.|4.|4.|4|εn
3812 |πand |εn|4.|4.|4.|42|41. |π(The variable |εx|βk
3817 |πappears in exactly |εF|βkF|βn|βα_↓|βk |πterms;
3822 hence |εx|β1 |πand |εx|βn |πcan only be permuted
3830 into |εx|β1 |πand |εx|βn. |πIf |εx|β1 |πand |εx|βn
3838 |πare _xed by the permutation, it follows by
3846 induction that |εx|β2,|4.|4.|4.|4,|4x|βn|βα_↓|β1
3849 |πare also _xed.)|'{A3}|1|9|≡8|≡.|4|9This is
3854 equivalent to|'{A9}|ε|(Q|βn|βα_↓|β2(A|βn|βα_↓|β1,|4.|4.|4.|4
3856 ,|4A|β2)|4α_↓|4XQ|βn|βα_↓|β1(A|βn|βα_↓|β1,|4.|4.|4.|4,|4A|β1
3856 )|d2Q|βn|βα_↓|β1(A|βn,|4.|4.|4.|4,|4A|β2)|4α_↓|4XQ|βn(A|βn,|
3856 4.|4.|4.|4,|4A|β1)|)|4α=↓|4α_↓|(1|d2X|βn|)|4,|;
3857 |π{A9}and by (6) this is equivalent to|'{A9}*?*?|εX|4α=↓|4|(Q|
3864 βn|βα_↓|β1(A|β2,|4.|4.|4.|4,|4A|βn)|4α+↓|4X|βnQ|βn|βα_↓|β2(A
3864 |β2,|4.|4.|4.|4,|4A|βn|βα_↓|β1|d2Q|βn(A|β1,|4.|4.|4.|4,|4A|β
3864 n)|4α+↓|4X|βnQ|βn|βα_↓|β1(A|β1,|4.|4.|4.|4,|4A|βn|βα_↓|β1)|)
3864 |4.|;{A9}|π|1|9|≡9|≡.|4|9(a) By de_nition. (b),
3869 (d) Prove this when |εn|4α=↓|41, |πthen apply
3876 (a) to get the result for general |εn. |π(c)
3885 Prove when |εn|4α=↓|4k|4α+↓|41, |πthen apply
3890 (a).|'{A3}|≡1|≡0|≡.|4|9If |εA|β0|4|¬Q|40, |πthen
3894 |εB|β0|4α=↓|40, B|β1|4α=↓|4A|β0, B|β2|4α=↓|4A|β1,
3897 B|β3|4α=↓|4A|β2, B|β4|4α=↓|4A|β3, B|β5|4α=↓|4A|β4,
3900 m|4α=↓|45. |πIf |εA|β0|4α=↓|40, |πthen |εB|β0|4α=↓|4A|β1,
3905 B|β1|4α=↓|4A|β2, B|β2|4α=↓|4A|β3, B|β3|4α=↓|4A|β4,
3908 m|4α=↓|43. |πIf |εA|β0|4α=↓|4|→α_↓1 |πand |εA|β1|4α=↓|41,
3913 |πthen |εB|β0|4α=↓|4|→α_↓(A|β2|4α+↓|42), B|β1|4α=↓|41,
3916 B|β2|4α=↓|4A|β3|4α_↓|41, B|β3|4α=↓|4A|β4, m|4α=↓|43.
3919 |πIf |εA|β0|4α=↓|4|→α_↓1 |πand |εA|β1|4|≡Q|41,
3923 |πthen |εB|β0|4α=↓|4|→α_↓2, B|β2|4α=↓|4A|β1|4α_↓|42,
3926 B|β3|4α=↓|4A|β2, B|β4|4α=↓|4A|β3, B|β5|4α=↓|4A|β4,
3929 m|4α=↓|45. |πIf |εA|β0|4|¬W|4|→α_↓1, |πthen |εB|β0|4α=↓|4|→α
3933 _↓1, B|β1|4α=↓|41, B|β2|4α=↓|4|→α_↓A|β0|4α_↓|42,
3936 B|β3|4α=↓|41, B|β4|4α=↓|4A|β1|4α_↓|41, B|β5|4α=↓|4A|β2,
3939 B|β6|4α=↓|4A|β3, B|β7|4α=↓|4A|β4. |π[Actually,
3942 the last three cases involve eight subcases;
3949 if any of the |εB'|πs is set to zero, the values
3960 should be ``collapsed together'' by using the
3967 rule of exercise 9(c). For example, if |εA|β0|4α=↓|4|→α_↓1,
3975 A|β1|4α=↓|4A|β3|4α=↓|41, |πwe actually have |εB|β0|4α=↓|4|→α
3979 _↓(A|β2|4α+↓|42), B|β1|4α=↓|4A|β4|4α+↓|41, m|4α=↓|41.
3982 |πDouble collapsing occurs when |εA|β0|4α=↓|4|→α_↓2,
3987 A|β1|4α=↓|41.]|'|H*?*?*?*?58320#Computer Programming!(Knuth/A.-W
folio 777 galley 7 WARNING: Couldn't read the beginning of this galley.
3989 .)!f. 777!ch. 4!g. 7c|'{A12}|π|≡1|≡1|≡.|4|9Let
3994 |εq|βn|4α=↓|4Q|βn(A|β1,|4.|4.|4.|4,|4A|βn), q|ur|↔0|)n|)|4α=
3995 ↓|4Q|βn(B|β1,|4.|4.|4.|4,|4B|βn), p|βn|4α=↓|4Q|βn|βα+↓|β1(A|
3996 β0,|4.|4.|4.|4,|4A|βn), p|ur|↔0|)n|)|4α=↓|4Q|βn|βα+↓|β1(B|β0
3997 ,|4.|4.|4.|4,|4B|βn). |πWe have |εX|4α=↓|4(p|βm|4α+↓|4p|βm|β
4000 α_↓|β1X|βm)/(q|βm|4α+↓|4q|βm|βα_↓|β1X|βm), Y|4α=↓|4(p|ur|↔0|
4001 )n|)|4α+↓|4p|ur|↔0|)nα_↓1|)Y|βn)/(q|ur|↔0|)n|)|4α+↓|4q|ur|↔0
4001 |)nα_↓1|)Y|βn); |πtherefore if |εX|βm|4α=↓|4Y|βn,
4005 |πthe stated relation between |εX |πand |εY |πholds
4013 by (8). conversely, if |εX|4α=↓|4(qY|4α+↓|4r)/(sY|4α+↓|4t),
4018 |¬Gqt|4α_↓|4rs|¬G|4α=↓|41, |πwe may assume that
4023 |εs|4|¬R|40, |πand we can show that the partial
4031 quotients of |εX |πand |εY |πeventually agree
4038 by induction on |εs. |πThe result is clear when
4047 |εs|4α=↓|40, |πby exercise 9(d). |πIf |εs|4|¬Q|40,
4053 |πlet |εq|4α=↓|4as|4α+↓|4s|¬S (0|4|¬E|4s|¬S|4|¬W|4s).
4056 |πThen |εX|4α=↓|4a|4α+↓|41/{H11}({H9}(sY|4α+↓|4t)/(s|¬SY|4α+
4057 ↓|4r|4α_↓|4at){H11}){H9}; |πsince |εs(r|4α_↓|4at)|4α_↓|4ts|¬
4059 S|4α=↓|4sr|4α_↓|4tq, |πand |εs|¬S|4|¬W|4s, |πwe
4063 know by induction and exercise 10 that the partial
4072 quotients of |εX |πand |εY |πeventually agree.
4079 [|εNote|*/: |\|πThe fact that |εm |πis always
4086 odd in exercise 10 shows, by a close inspection
4095 of this proof, that|πBut by (12), |εp|βn|βα_↓|β1/q|βn|βα_↓|β
4101 1/q|βn|βα_↓|β1 |πand |εp|βn/q|βn |πare extremely
4106 close to |εX; |πsince |εX|4|=|↔6α=↓|4Y, Y|4α_↓|4p|βn/q|βn
4112 |πand |εY|4α_↓|4p|βn|βα_↓|β1/q|βn|βα_↓|β1 |πwill
4115 have the same sign as |εY|4α_↓|4X |πfor all large
4124 |εn. |πThis proves that |εY|βn|4|¬W|40 |πfor
4130 all large |εn; |πhence 0|4|¬W|4|εX|βn|4|¬W|4X|βn|4α_↓|4Y|βn|
4134 4α=↓|42|¬H|v4D|)/V|βn; V|βn |πmust be positive.
4139 Also |εU|βn|4|¬W|4|¬H|v4D|), |πsince |εX|βn|4|¬Q|40.
4143 |πHence |εV|βn|4|¬W|42|¬H|v{A9}|(|→α_↓V|βn|βα+↓|β1|d2V|βn|)|
4144 4α=↓|4X|βnY|βn|4α=↓|4|((q|βnX|4α_↓|4p|βn)(q|βnY|4α_↓|4p|βn)|
4144 d2(q|βn|βα_↓|β1X|4α_↓|4p|βn|βα_↓|β1)(q|βn|βα_↓|β1Y|4α_↓|4p|β
4144 n|βα_↓|β1)|)|4.|;{A9}|π[A companion identity
4148 is|'{A9}|εVp|βnp|βn|βα_↓|β1|4α+↓|4U(p|βnq|βn|βα_↓|β1|4α+↓|4p
4149 |βn|βα_↓|β1q|βn)|4α+↓|4{H11}({H9}(U|g2|4α_↓|4D)/V{H11}){H9}q
4149 |βnq|βn|βα_↓|β1|4α=↓|4(|→α_↓1)|gnU|βn.]|;{A9}|π!!|1|1(d)|9If
4150 |εX|βn|4α=↓|4X|βm |πfor |εn|4|=|↔6α=↓|4|εm,
4154 |πthen |εX |πis an irrational number which satis_es
4162 the quadratic equation |ε(q|βnX|4α_↓|4p|βn)/(q|βn|βα_↓|β1X|4
4165 α_↓|4p|βn|βα_↓|β1|4α=↓|4(q|βmX|4α_↓|4p|βm)/(q|βm|βα_↓|β1X|4α
4165 _↓|4p|βm|βα_↓|β1).|'|π|≡1|≡4|≡.|4|9As in exercise
4169 9, we need only verify the stated identities
4177 when |εc |πis the last partial quotient, and
4185 this veri_cation is trivial. Now Hurwitz's rule
4192 gives |ε2/e|4α=↓|4|"C), 2, 1, 2, 0, 1, 1, 1,
4201 1, 1, 0, 2, 3, 2, 0, 1, 1, 3, 1, 1, 0, 2, 5,|4.|4.|4.|"C.
4216 |πTaking the receiprocal, collapsing out the
4222 zeros as in exercise 9, and taking note of the
4232 pattern that appears, we _nd that (cf. exercise
4240 16) |εe/2|4α=↓|41|4α+↓|4|"C2, 2m|4α+↓|41,|43,|41,|42m|4α+↓|4
4242 1,|41,|43|"C, m|4|¬R|40. [Schriften der phys.-|=4okon.
4247 Gesellschaft zu K|=4onigsberg |≡3|≡2 (1891),
4252 59<62.]|'{A3}{U0}{H9L11M29}|≡1|≡5|≡.|4|9{H11}({H9}This
4254 procedure maintains four integers (|εA, B, C,
4261 D) |πwith the invariant meaning that ``our remaining
4269 job is to output the continued fraction for |ε(Ay|4α+↓|4B)/(
4277 Cy|4α+↓|4D), |πwhere |εy |πis the input yet to
4285 come.``{H11}){H9} Initially set |εj|4|¬L|4k|4|¬L|40,
4289 (A, B, C, D)|4|¬L|4(a, b, c, d); |πthen input
4298 |εx|βj |πand set (|εA, B, C, D)|4|¬L|4(Ax|βj|4α+↓|4B,
4305 A, Cx|βj|4α+↓|4D, C), j|4|¬L|4j|4α+↓|41, |πone
4310 or more times until |εC|4α+↓|4D |πhas the same
4318 sign as |εC. {H11}({H9}|πWhen |εj|4|¬R|41 |πand
4324 the input has not terminated, we know that |ε1|4|¬W|4y|4|¬W|
4332 4|¬X; |πand when |εC|4α+↓|4D |πhas the same sign
4340 as |εC |πwe know therefore that (|εAy|4α+↓|4B)/(Cy|4α+↓|4D)
4347 |πlies between |ε(A|4α+↓|4B)/(C|4α+↓|4D) |πand
4351 |εA/C.{H11}){H9} |πNow comes the general step:
4357 If no integer lies strictly between (|εA|4α+↓|4B)/(C|4α+↓|4D
4363 ) |πand |εA/C, |πoutput |εX|βk|4|¬L|4|"lA/C|"L,
4368 |πand set |ε(A, B, C, D)|4|¬L|4(C, D, A|4α_↓|4X|βkC,
4376 B|4α_↓|4X|βkD), k|4|¬L|4k|4α+↓|41; |πotherwise
4379 input |εx|βj |πand set |ε(A, B, C, D)|4|¬L|4(Ax|βj|4α+↓|4B,
4387 A, Cx|βj|4α+↓|4D, C), j|4|¬L|4j|4α+↓|41. |πThe
4392 general step is repeated ad in_nitum. However,
4399 if at any time the |ε⊂nal |εx|βj |πis input,
4408 the algorithm immediately switches gears: It
4414 outputs the continued fraction for |ε(Ax|βj|4α+↓|4B)/(Cx|βj|
4419 4α+↓|4D), |πusing Euclid's algorithm, and terminates.|'
4425 !!|1|1The following tableau shows the working
4431 for the requested example, where the matrix |ε|↔a|(b!A|d5D!C
4438 |)|↔s |πbegins at the upper left corner then
4446 shifts right one on input, down one on output.|'
4455 {A12}|∂!!!|∂!!!|∂!!!|∂!!!|∂!!!|4|1|1|∂!!!|∂!!!|∂!!!|∂!!!|∂!!
4455 !|∂!!!|∂|E|;|J#>|>|;|εx|βj|;|→α_↓1|;5|;1|;1|;
4464 1|;2|;1|;2|;|¬X|;>{B2}|J#>|>!X|βk:|'|9|4|439|;
4474 |9|4|497|;|9|4|458|;|4|4|9193|;|;|;|;|;|;|;>|>
4485 !|>|→α_↓2|'|→α_↓25|;|→α_↓62|;|4|4|937|;|4|4|9123|;
4491 >|>!|4|4|9|92|'|;|;|4|4|916|;|4|4|9|9|153|;>|>
4500 !|4|4|93|'|;|;|4|4|9|9|15|;|9|4|4|9|117|;22|;
4506 39|;>|>!|4|4|97|'|;|;|4|4|9|9|11|;|4|4|9|4|4|4|4|42|;
4514 |9|13|;|9|15|;8|;>|>!|4|4|91|'|;|;|;|;|1|91|;
4525 |1|94|;5|;14|;>|>!|4|4|91|'|;|;|;|;|;|9|11|;3|;
4538 |9|17|;>|>!|4|4|91|'|;|;|;|;|;|;2|;|9|17|;9|;
4551 25|;>|>!|413|'|;|;|;|;|;|;1|;|9|10|;1|;|9|12|;
4565 >|>!|4|4|92|'|;|;|;|;|;|;|;|;|;|9|11|;>|>!|¬X|'
4581 |;|;|;|;|;|;|;|;|;|1|90|;>{A12}{H9L11M25}|π!!|1|1M.
4593 Mend|=2es France has shown that the number of
4601 quotients output per quotient input is asymptotically
4608 bounded between 1/|εr |πand |εr, |πwhere |εr|4α=↓|42|"lK(|¬G
4614 ad|4α_↓|4bc|¬G)/2|"L|4α+↓|41 |πand |εK |πis the
4619 function de_ned in exercise 38; this bound is
4627 best possible. |ε[Colloquia Math. Soc. J|=1anos
4633 Bolyai, |πDebrecen, 1974, to appear.]|'!!|1|1The
4639 above algorithm can be generalized to compute
4646 the continued traction for |ε(axy|4α+↓|4bx|4α+↓|4cy|4α+↓|4d)
4650 /(Axy|4α+↓|4Bx|4α+↓|4Cy|4α+↓|4D) |πfrom those
4653 of |εx |πand |εy |π(in particular, to compute
4661 sums an{U0}{H9L11M29}58320#Computer Programming!(Knuth/A.-W.
folio 781 galley 8
4663 )!f. 781!ch. 4!g. 8c|'{A12}|≡1|≡6|≡.|4|9It is
4669 not di∃cult to prove by induction that |εf|βn(z)|4α=↓|4z/(2n
4676 |4α+↓|41)|4α+↓|4O(z|g3) |πis an odd function
4681 with a convergent power series in a neighborhood
4689 of the origin, and that it satis_es the given
4698 di=erential equation. Hence|'{A9}|εf|β0(z)|4α=↓|4|"Cz|gα_↓|g
4701 1|4α+↓|4f|β1(z)|"C|4α=↓|4|¬O|4|¬O|4|¬O|4α=↓|4|"Cz|gα_↓|g1,|4
4701 3z|gα_↓|g1,|4.|4.|4.|4,|4(2n|4α+↓|41)z|gα_↓|g1|4α+↓|4f|βn|βα
4701 +↓|β1(z)|"C.|;{A9}|πIt remains to prove that
4707 lim|ur|)|εn|¬M|¬X|)|"Cz|gα_↓|g1, 3z|gα_↓|g1,|4.|4.|4.|4,|4(2
4708 n|4α+↓|41)z|gα_↓|g1|"C|4α=↓|4f|β0(z). |π[Actually
4710 Euler, age 24, obtained continued fraction expansions
4717 for the considerably more general di=erential
4723 equation |εf|ur|↔0|)n|)(z)|4α=↓|4az|gm|4α+↓|4bf|βn(z)z|gm|gα
4724 _↓|g1|4α+↓|4cf|βn(z)|g2; |πbut he did not bother
4730 to prove convergence, since formal manipulation
4736 and intuition were good enough in the eighteenth
4744 century.]|'!!|1|1There are several ways to prove
4751 the desired limiting equation. First, letting
4757 |εf|βn(z)|4α=↓|4|¬K|βk|4a|βn|βkz|gk, |πwe can
4760 argue from the equation|'{A9}|ε!(2n|4α+↓|41)a|βn|β1|4α+↓|4(2
4764 n|4α+↓|43)a|βn|β3z|g2|4α+↓|4(2n|4α+↓|45)a|βn|β5z|g4|4α+↓|1|1
4764 |¬O|4|¬O|4|¬O|'{A4}α=↓|41|4α_↓|4(a|β1z|4α+↓|4a|β3z|g3|4α+↓|4
4765 a|β5z|g5|4α+↓|1|1|¬O|4|¬O|4|¬O)|g2!|?{A9}|πthat
4767 (|→α_↓1)|ε|gka|βn|β(|β2|βk|βα+↓|β1|β) |πis a
4770 sum of terms of the form |εc|βk/(2n|4α+↓|41)|gk|gα+↓|g1(2n|4
4776 α+↓|4b|βk|β1)|4.|4.|4.|4(2n|4α+↓|4b|βk|βk), |πwhere
4778 the |εc|βk |πand |εb|βk|βm |πare positive integers
4785 independent of |εn. |πFor example, |ε|→α_↓a|βn|β7|4α=↓|44/(2
4790 n|4α+↓|41)|g4(2n|4α+↓|43)(2n|4α+↓|45)(2n|4α+↓|47)|4α+↓|41/(2
4790 n|4α+↓|41)|g4(2n|4α+↓|43)|g2(2n|4α+↓|47). |πThus
4792 |ε|¬Ga|ur|)(nα+↓1)k|)|¬G|4|¬E|4|¬Ga|βn|βk|¬G,
4793 |πand |ε|¬G|1f|βn(z)|¬G|4|¬E|4|πtan |ε|¬Gz|¬G
4796 |πfor |ε|¬Gz|¬G|4|¬W|4|≤p/2. |πThis uniform bound
4801 on |εf|βn(z) |πmakes the convergence proof very
4808 simple. Careful study of this argument reveals
4815 that the power series for |εf|βn(z) |πactually
4822 converges for |ε|¬Gz|¬G|4|¬W|4|≤p|¬H|v42n|4α+↓|41|)/2;
4825 |πthis is interesting, since it shows that the
4833 singularities of |εf|βn(z) |πget farther and
4839 farther away from the origin as |εn |πgrows,
4847 so the continued fraction actually represents
4853 tanh |εz throughout |πthe complex plane.|'!!|1|1Another
4860 proof gives further information of a di=erent
4867 kind: If we let|'!!|1|1Another proof gives further
4875 information of a di=erent kind: If we let|'{A9}|εA|βn(z)|4α=
4883 ↓|4n*3|4|↔k|uc|)0|¬Ek|¬En|)|4|↔a|(2n|4α_↓|4k|d5n|)|↔sz|gk|↔hk
4883 *3|4α=↓|4|↔k|uc|)k|¬R0|)|4|((n|4α+↓|4k)*3z|gn|gα_↓|gk|d2k*3(n|4
4883 α_↓|4k)*3|)|4,|;{A9}|πthen|'{A9}|εA|βn|βα+↓|β1(z)|4α=↓|4|↔k|u
4885 c|)k|¬R0|)|4|((n|4α+↓|4k|4α_↓|41)*3{H11}({H9}(4n|4α+↓|42)k|4α
4885 +↓|4(n|4α+↓|41|4α_↓|4k)(n|4α_↓|4k){H11})|d2{H9}k*3(n|4α+↓|41|
4885 4α_↓|4k)*3|)|4z|gn|gα+↓|g1|gα_↓|gk|;{A4}**************α=↓|4(4n|4α+↓|
4886 42)A|βn(z)|4α+↓|4z|g2A|βn|βα_↓|β1(z).|;{A9}|πIt
4888 follows, by induction, that|'{A9}|εQ|βn|↔a|(1|d2z|),|4|(3|d2
4892 z|)|4,|4.|4.|4.|4,|4|(2n|4α_↓|41|d2z|)|↔s|4|∂α=↓|4|(A|βn(2z)
4892 |4α+↓|4A|βn(|→α_↓2z)|d22|gn|gα+↓|g1z|gn|)|4,|;
4893 {A4}| Q|βn|βα_↓|β1|↔a|(3|d2z|)|4,|4.|4.|4.|4,|4|(2n|4α_↓|41|
4893 d2z|)|↔s|4|Lα=↓|4|(A|βn(2z)|4α_↓|4A|βn(|→α_↓2z)|d22|gn|gα+↓|
4893 g1z|gn|)|4.>{A9}|πHence|'|ε|"Cz|gα_↓|g1,|43z|gα_↓|g1,|4.|4.|
4895 4.|4,|4(2n|4α_↓|41)z|gα_↓|g1|"C|4α=↓|4|(A|βn(2z)|4α_↓|4A|βn(
4895 |→α_↓2z)|d2A|βn(2z)|4α+↓|4A|βn(|→α_↓2z)|)|4,|;
4896 {A9}|πand we want to show that this ratio approaches
4905 tanh |εz. |πBy Eqa. 1.2.9<11 and 1.2.6<26,|'{A9}|εe|gzA|βn(|
4912 →α_↓z)|4α=↓|4n*3|4|↔k|uc|)m|¬R0|)|4z|gm{H12}|↔a{H9}|↔k|uc|)0|
4912 ¬Ek|¬En|)|4|↔a|(m|d5k|)|↔s|↔a|(2n|4α_↓|4k|d5n|)|↔s(|→α_↓1)|g
4912 k{H12}|↔s{H9}|4|↔k|uc|)m|¬R0|)|4|↔a|(2n|4α_↓|4m|d5n|)|↔sz|gm
4912 |4|(n*3|d2m*3|)|4.|;{A9}|πHence|'{A9}|εe|gzA|βn(|→α_↓z)|4α_↓|4
4914 A|βn(z)|4α=↓|4R|βn(z)|4α=↓|4(|→α_↓1)|gnx|g2|gn|gα+↓|g1|4|↔k|
4914 uc|)k|¬R0|)|4|((n|4α+↓|4k)*3x|gk|d2(2n|4α+↓|4k|4α+↓|41)*3k*3|)|
4914 4.|;{A9}|π{H9L11M29}We now have (|εe|g2|gz|4α_↓|41){H11}({H9
4918 }A|βn(2z)|4α+↓|4A|βn(|→α_↓2z){H11}){H9}|4α_↓|4(e|g2|gz|4α+↓|
4918 41){H11}({H9}A|βn(2z)|4α_↓|4A|βn(|→α_↓2z){H11}){H9}|4α=↓|42R
4918 |βn(2z); |πhence|'{A9}{H9L11M29}|ε|"Cz|gα_↓|g1,|43z|gα_↓|g1,
4920 |4.|4.|4.|4,|4(2n|4α_↓|41)z|gα_↓|g1|"C|4α=↓|4|(2R|βn(2z)|d2{
4920 H11}({H9}A|βn(2z)|4α+↓|4A|βn(|→α_↓2z){H11}){H9}(e|g2|gz|4α+↓
4920 |41)|)|4.|;{A9}{H9L11M29}|πThus we have an exact
4926 formula for the di=erence. When |ε|¬Gz|¬G|4|¬E|4|f1|d32|),
4932 e|g2|gz|4α+↓|41 |πis bounded away from zero,
4938 |ε|¬GR|βn(2z)|¬G|4|¬E|4en*3/(2n|4α+↓|41)*3, |πand|'
4940 {A9}|ε|f1|d32|)|¬GA|βn(2z)|4α+↓|4A|βn(|→α_↓2z)|¬G|4|¬R|4n*3{H
4940 12}|↔a{H9}|↔a|(2n|d5n|)|↔s|4α_↓|4|↔a|(2n|4α_↓|42|d5n|)|↔s|4α
4940 _↓|4|↔a|(2n|4α_↓|44|d5n|)|↔s|4α_↓|1|1|¬O|4|¬O|4|¬O{H12}|↔s|;
4941 {A4}|¬R|4|((2n)*3|d2n*3|)|4(1|4α_↓|4|f1|d34|)|4α_↓|4|f1|d316|)
4941 |4α_↓|1|1|¬O|4|¬O|4|¬O)|4α=↓|4|(2|d23|)|4|((2n)*3|d2n*3|)|4.|;
4942 {A9}{H9L11M29}|πThus convergence is very rapid,
4947 even for complex values of |εz.|'|π!!|1|1To go
4955 from this continued fraction to the continued
4962 fraction for |εe|gz, |πwe have tanh |εz|4α=↓|41|4α_↓|42/(e|g
4968 2|gz|4α+↓|41); |πhence we get the continued fraction
4975 representation for |ε(e|g2|gz|4α+↓|41)/2 |πby
4979 simple manipulations. Hurwitz's rule gives the
4985 expansion of |εe|g2|gz|4α+↓|41, |πfrom which
4990 we may subtract unity. For |εn |πodd,|' {A9}|εe|gα_↓|g2|g/|g
4998 n|4α=↓|4|"C1,|43mn|4α+↓|4|"ln/2|"L,|4(12m|4α+↓|46)n,|4(3m|4α
4998 +↓|42)n|4α+↓|4|"ln/2|"L,|41|"C,!!m|4|¬R|40.|;
4999 !!|1|1|πAnother derivation has been given by
5005 C. S. Davis, |εJ. London Math. Soc. |≡2|≡0 (1945),
5014 194<198.|'{A3}{H9L11M29}|π|≡1|≡7|≡.|4|9(b)|4|4|"C|εx|β1|4α_↓
5015 |41, 1, x|β2|4α_↓|42, 1, x|β3|4α_↓|42, 1,|4.|4.|4.|4,|41,
5021 x|β2|βn|βα_↓|β1|4α_↓|42, 1, x|β2|βn|4α_↓|41|"C.|'
5024 !!|1|1(c)|1|91|4α+↓|4|"C1, 1, 3, 1, 5, 1,|4.|4.|4.|"C.|'
5030 {A3}|π|≡1|≡9|≡.|4|9The sum for |ε1|4|¬E|4k|4|¬E|4N
5034 |πis log|ε|βb {H11}({H9}2|4|¬O|43|4.|4.|4.|4(N|4α+↓|41){H11}
5036 ){H9}|4α_↓|4|πlog|ε|βb (1|4|¬O|42|4.|4.|4.|4N)|4α_↓|4|πlog|ε
5037 |βb {H11}({H9}(2|4α+↓|4x)(3|4α+↓|4x)|4.|4.|4.|4(N|4α+↓|41|4α
5038 +↓|4x){H11}){H9}|4α+↓|4|πlog|ε|βb {H11}({H9}(1|4α+↓|4x)(2|4α
5039 +↓|4x)|4.|4.|4.|4(N|4α+↓|4x){H11}){H9}|4α=↓|4|πlog|ε|βb
5040 {H11}({H9}(1|4α+↓|4x)(N|4α+↓|41)/(N|4α+↓|41|4α+↓|4x){H11}){H
5040 9}.|'{A3}{H9L11M29}|π|≡2|≡0|≡.|9|4Let |εH|4α=↓|4SG,
5043 g(x)|4α=↓|4(1|4α+↓|4x)G|¬S(x), h(x)|4α=↓|4(1|4α+↓|4x)H|¬S(x)
5044 . |πThen (35) implies that |εh(x|4α+↓|41)/(x|4α+↓|42)|4α_↓|4
5049 h(x)/(x|4α+↓|41)|4α=↓|4|→α_↓(1|4α+↓|4x)|gα_↓|g2g(1/(1|4α+↓|4
5049 ){H11}){H9}/{H11}({H9}1|4α+↓|41/(1|4α+↓|4x){H11}){H9}.|'
5050 {A3}|π|≡2|≡1|≡.|9|4|ε|≤'(x)|4α=↓|4c/(cx|4α+↓|41)|g2|4α+↓|4(2
5050 |4α_↓|4c)/{H11}({H9}(c|4α_↓|41)x|4α+↓|41{H11}){H9}|g2,
5051 U|≤'(x)|4α=↓|41/(x|4α+↓|4c)|g2. |πWhen |εc|4|¬E|41,
5054 |πthe minimum of |ε|≤'(x)/U|≤'(x) |πoccurs at
5060 |εx|4α=↓|40 |πand is |ε2c|g2|4|¬E|42. |πWhen
5065 |εc|4|¬R|4|≤f|4α=↓|4|f1|d32|)(|¬H|v45|)|4α+↓|41),
5066 |πthe minimum occurs at |εx|4α=↓|41 |πand is
5073 |→|¬E|ε|≤f|g2. |πWhen |εc|4|¬V|41.31266 |πthe
5077 values at |εx|4α=↓|40 |πand |εx|4α=↓|41 |πare
5083 nearly equal and the minimum is |→|¬Q3.2; the
5091 bounds (0.29)|ε|gn|≤'|4|¬E|4U|gn|≤'|4|¬E|4(0.31)|gn|≤'
5093 |πare obtained. Still bounds come from well-chosen
5100 linear combinations |εTg(x)|4α=↓|4|¬K|4a|βj/(x|4α+↓|4c|βj).|
5102 '{A3}|π|≡2|≡3|≡.|4|9By the interpolation formula
5107 of exercise 4.64<15 with |εx|β0|4α=↓|40, x|β1|4α=↓|4x,
5113 x|β2|4α=↓|4x|4α+↓|4|≤e, |πletting |ε|≤e|4|¬M|40,
5116 |πwe have the general identity |εR|ur|↔0|)n|)(x)|4α=↓|4{H11}
5121 ({H9}R|βn(x)|4α_↓|4R|βn(0){H11})}h9}/x|4α+↓|4|f1|d32|)xR|βn{
5121 H11}({H9}|≤u(x){H11}){H9} |πfor some |ε|≤u(x)
5125 |πbetween 0 and |εx, |πwhenever |εR|βn |πis a
5133 function with continuous second derivative. Hence
5139 in this case |εR|ur|↔0|)n|)(x)|4α=↓|4O(2|gα_↓|gn).|'
5143 {A3}|π|≡2|≡4|≡.|4|9|¬X. [A. Khinchin, in |εcompos.
5148 Math. |≡1 (1935), 361<382, |πproved that the
5155 sum |εA|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4A|βn
5157 |πof the _rst |εn |πpartial quotients of a real
5166 number |εX |πwill be asymptotically |εn|4|πlg|4|εn,
5172 |πfor almost all |εX.]|'|Hβ*?*?*?*?{U0}{H9L11M29}58320#Computer
folio 784 galley 9
5177 Programming!(Knuth/A.-W.)!f. 784!ch. 4!g. 9c|'
5181 {A12}|π|≡2|≡5|≡.|4|9Any union of intervals can
5186 be written as a union of disjoint intervals,
5194 since |ε|↔w|βk|β|¬R|β1|4I|βk|4α=↓|4|↔w|βk|β|¬R|β1
5196 (I|βk|4α_↓|4|↔w|ur|)1|¬Ej|¬Wk|)|4I|βj), |πand
5198 this is a disjoint union in which |εI|βk|4α_↓|4|↔w|β1|β|¬E|β
5205 j|β|¬W|βk|4I|βj |πcan be expressed as a _nite
5212 union of disjoint intervals. Therefore we may
5219 take |ε|λI|4α=↓|4|↔w|4I|βk, |πwhere |εI|βk |πis
5224 an interval of length |ε|≤e/2|gk |πcontaining
5230 the |εk|πth rational number in [0,|41], using
5237 some enumeration of the rationals. In this case
5245 |ε|≤m(|λI-|4|¬E|4|≤e, |πbut |¬F|ε|λI|4|↔w|4P|βn|¬F|4α=↓|4n
5248 |πfor all |εn.|'{A3}|π|≡2|≡6|≡.|4|9The continued
5253 fractions |"C|εA|β1,|4.|4.|4.|4,|4A|βt|"C |πwhich
5256 appear are precisely those for which |εA|β1|4|¬Q|41,
5263 A|βt|4|¬Q|41, |πand |εQ|βt(A|β1, A|β2,|4.|4.|4.|4,|4A|βt)
5267 |πis a divisor of |εn. |πTherefore (6) completes
5275 the proof. {H11}({H9}|εNote|*/:|\ |πIf |εm|β1/n|4α=↓|4|"CA|β1
5279 ,|4.|4.|4.|4,|4A|βt|"C |πand |εm|β2/n|4α=↓|4|"CA|βt,|4.|4.|4
5281 .|4,|4A|β1|"C, |πwhere |εm|β1 |πand |εm|β2 |πare
5287 relatively prime to |εn, |πthen |εm|β1m|β2|4|"o|4|→|¬N1
5293 (|πmodulo |εn); |πthis rule de_nes the correspondence.
5300 When |εA|β1|4α=↓|41 |πan analogous symmetry is
5306 valid, according to (38).{H11}){H9}|'{A3}{H9L11M29}|≡2|≡7|≡.
5310 |4|9First prove the result for |εn|4α=↓|4p|ge,
5316 |πthen for |εn|4α=↓|4rs, |πwhere |εr |πand |εs
5323 |πare relatively prime. alternatively, use the
5329 formulas in the next exercise.|'{A3}{H9L11M29}|≡2|≡8|≡.|4|9(
5334 a) The left-hand side is multiplicative (see
5341 exercise 1.2.4<31), and it is easily evaluated
5348 when |εn |πis a power of a prime. (c) From (a),
5359 we have |εM|=4obius inversion formula|*/: |\|πIf
5365 |εf|1(n)|4α=↓|4|¬K|ur|)d|¬Dn|)|4g(d), |πthen
5367 |εg(n)|4α=↓|4|¬K|ur|)d|¬Dn|)|4|≤m(n/d)f|1(d).|'
5368 {A3}|π|≡2|≡9|≡.|4|9The sum is approximately (12|4ln|42/|ε|≤p
5372 |g2)|4|πln|4|εN*3/N|4α_↓|4|¬K|ur|)d|¬R1|)|4|*/|≤!|\(d)/d|g2|4α
5372 +↓|41.47; |πhere |ε|¬K|ur|)d|¬R1|)|4|*/|≤!|\(d)/d|g2
5375 |πconverges to the constant value |ε|→α_↓|≤z|¬S(2)/|≤z(2),
5381 |πwhile ln|4|εN*3|4α=↓|4N|4|πln|4|εN|4α_↓|4N|4α+↓|4O(|πlog|4|
5382 εN) |πby Stirling's approximation.|'{A3}|≡3|≡0|≡.|4|9The
5387 modi_ed algorithm a=ects the calculation if and
5394 only if the following division step in the unmodi_ed
5403 algorithm would have the quotient 1, and in this
5412 case it avoids the following division step. The
5420 probability that a given division step is avoided
5428 is the probability that |εA|βk|4α=↓|41 |πand
5434 that this quotient is preceded by an even number
5443 of quotients equal to 1. By the symmetry condition,
5452 this is the probability that |εA|βk|4α=↓|41 |πand
5459 is |εfollowed |πby an even number of quotients
5467 equal to 1. The latter happens if and only if
5477 |εX|βk|βα_↓|β1|4|¬Q|4|≤f|4α_↓|41|4α=↓|40.618|4.|4.|4.|4,
5478 |πwhere |ε|≤f |πis the golden ratio: For |εA|βk|4α=↓|41,
5486 A|βk|βα+↓|β1|4|¬Q|4|πi= |f2|d33|)|4|¬E|4|εX|βk|βα_↓|β1|4|¬W|
5487 41; A|βk|4α=↓|4A|βk|βα+↓|β1|4α=↓|4A|βk|βα+↓|β2|4α=↓|41,
5489 A|βk|βα+↓|β3|4|¬Q|41 |πi= |f5|d38|)|4|¬E|4|εX|βk|βα_↓|β1|4|¬
5491 W|4|f2|d33|); |πetc. Thus we save approximately
5497 |εF|βk|βα_↓|β1(1)|4α_↓|4F|βk|βα_↓|β1(|≤f|4α_↓|41)|4|¬V|41|4α
5497 _↓|4|πlg|β2|4|ε|≤f|4|¬V|40.306 |πof the division
5501 steps. The average number of steps is approximately
5509 (12|4ln|4|ε|≤f/|≤p|g2)|πln|4|εn, |πwhen |εv|4α=↓|4n
5512 |πand |εu |πis relatively prime to |εn. |πKronecker
5520 [|εVorlesungen |=4uber Zahlentheorie |≡1 |π(Leipzig:
5525 Teubner, 1901), 118] observed that this choice
5532 of least remainder in absolute value always gives
5540 the shortest possible number of iterations, over
5547 all algorithms which replace |εu |πby |ε(|→|¬Nu)|πmod
5554 |εv |πat each iteration. For further results
5561 see N. G. de Bruijn and W. M. Zaring, |εNieuw
5571 Archief voor Wiskunde (3) |≡1 (1953), 105<112.|'
5578 |π!!|1|1On many computers, the modi_ed algorithm
5584 makes each division step longer; the idea of
5592 exercise 1, which saves |εall |πdivision steps
5599 when the quotient is unity, would be preferable
5607 in such cases.|'{A3}|≡3|≡1|≡.|4|9Let |εa|β0|4α=↓|40,
5612 a|β1|4α=↓|41, a|βn|βα+↓|β1|4α=↓|42a|βn|4α+↓|4a|βn|βα_↓|β1;
5614 |πthen |εa|βn|4α=↓|4{H11}({H9}(1|4α+↓|4|¬H|v42|))|gn|4α_↓|4(
5615 1|4α_↓|4|¬H|v42|))|gn{H11}){H9}/2|¬H|v42|), |πand
5617 the worst case (in the sense of Theorem F) occurs
5627 when |εu|4α=↓|4a|βn|4α+↓|4a|βn|βα_↓|β1, v|4α=↓|4a|βn,
5630 n|4|¬R|42.|'|π!!|1|1This result is due to A.
5637 Dupr|=⊂e [|εJ. de Math. |≡1|≡1 (1846), 41<64],
5644 |πwho also investigated more general ``look-ahead''
5650 procedures suggested by J. Binet. See P. Bachmann,
5658 |εNiedere Zahlentheorie |≡1 (|πLeipzig: Teubner,
5663 1902), 99<118, for a discussion of early analyses
5671 of Euclid's algorithm.|'{A3}|≡3|≡2|≡.|4|9|εQ|βm|βα_↓|β1(x|β1
5674 ,|4.|4.|4.|4,|4x|βm|βα_↓|β1)Q|βn|βα_↓|β1(x|βm|βα+↓|β2,|4.|4.
5674 |4.|4,|4x|βm|βα+↓|βn) |πcorresponds to Morse
5678 code sequence of length |ε(m|4α+↓|4n) |πin which
5685 a dash occupies positions |εm |πand |ε(m|4α+↓|41);
5692 |πthe other term corresponds to the opposite
5699 case. (Alternatively, use exercise 2. Actually
5705 Euler gave the more general identity |εQ|βm|βα+↓|βn(x|β1,|4.
5711 |4.|4.|4,|4x|βm|βα+↓|βn)Q|βk(x|βm|βα+↓|β1,|4.|4.|4.|4,|4x|βm
5711 |βα+↓|βk)|4α=↓|4Q|βm|βα+↓|βk(x|β1,|4.|4.|4.|4,|4x|βm|βα+↓|βk
5711 )Q|βn(x|βm|βα+↓|β1,|4.|4.|4.|4,|4x|βm|βα+↓|βn)|4α+↓|4(|→α_↓1
5711 )|gkQ|βm|βα_↓|β1(x|β1,|4.|4.|4.|4,|4x|βm|βα_↓|β1)Q|βn|βα_↓|β
5711 k|βα_↓|β1(x|βm|βα+↓|βk|βα+↓|βz,|4.|4.|4.|4,|4x|βm|βα+↓|βn).{
5711 H11}){H9}|'{A3}|π|≡3|≡3|≡.|4|9(a) The new representations
5716 are |εx|4α=↓|4m/d, y|4α=↓|4(n|4α_↓|4m)/d, x|¬S|4α=↓|4y|¬S|4α
5719 =↓|4d|4α=↓|4|πgcd(|εm,|4n|4α_↓|4m), |πfor |f1|d32|)|εn|4|¬W|
5721 4m|4|¬W|4n. |π(b) The relation |ε(n/x|¬S)|4α_↓|4y|4|¬E|4x|4|
5725 ¬W|4n/x|¬S |πde_nes |εx. |π(c) Count the |εx|¬S
5732 |πsatisfying (b). (d) A pair of integers |εx|4|¬Q|4y|4|¬Q|40
5739 , |πgcd(|εx,|4y|4α=↓|41), |πcan be uniquely written
5745 in the form |εx|4α=↓|4Q|βm(x|β1,|4.|4.|4.|4,|4x|βm),
5749 y|4α=↓|4Q|βm|βα_↓|β1(x|β1,|4.|4.|4.|4,|4x|βm|βα_↓|β1),
5750 |πwhere |εx|β1|4|¬R|42, m|4|¬R|41; |πhere |εy/x|4α=↓|4|"Cx|β
5754 m,|4.|4.|4.|4,|4x|β1|"C. |π(e) It su∃ces to show
5760 that |ε|¬K|ur|)1|¬Ek|¬En/2|)T(k,|4n)|4α=↓|42|"ln/2|"L|4α+↓|4
5761 h(n). |πFor |ε1|4|¬E|4k|4|¬E|4n/2 |πthe continued
5766 fractions |εk/n|4α=↓|4|"Cx|β1,|4.|4.|4.|4,|4x|βm)|¬Dn;
5768 |πand |εT(k,|4n)|4α=↓|42|4α+↓|4(m|4α_↓|41).|'
5770 {A3}{H9L11M29}|π|≡3|≡4|≡.|4|9(a) Dividing |εx,
5773 y |πby gcd(|εx,|4y) |πyields |εg(n)|4α=↓|4|¬K|ur|)d|¬Dn|)|4h
5777 (n/d); |πapply exercise 28(c), and use the symmetry
5785 between primed and unprimed variables. (b) For
5792 _xed |εy |πand |εt |πthe representations with
5799 |εxd|4|¬R|4x|¬S |πhave |εx|¬S|4|¬W|4|¬H|v4nd|);
5802 |πhence there are |εO(|¬H|v4nd|)/y) |πsuch representations.
5808 Now sum for |ε0|4|¬W|4t|4|¬E|4y|4|¬W|4|¬H|v4n/d|).
5812 |π(c) If |εs(y) |πis the given sum, then |ε|¬K|ur|)d|¬Dy|)|4
5820 s(d)|4α=↓|4y(H|β2|βy|4α_↓|4H|βy)|4α=↓|4k(y),
5821 |πsay; hence |εs(y)|4α=↓|4|¬K|ur|)d|¬Dy|)|4k(y/d).
5824 |πNow |εk(y)|4α=↓|4y|4|πln|42|4α_↓|4|f1|d34|)|4α+↓|4|εO(1/y)
5825 . |π(d) |ε|¬K|ur|)1|¬Ey|¬En|)|4|≤'(y)/y|g2|4α=↓|4|¬K|ur|)1|¬
5827 Ey|¬En,d|¬Dy|)|4|≤m(d)/yd|4α=↓|4|¬K|ur|)cd|¬En|)|4|≤m(d)/cd|
5827 g2. (|πsimilarly, |ε|¬K|ur|)1|¬Ey|¬En|)|4|≤s|βα_↓|β1(y)/y|g2
5829 |4α=↓|4O(1).{H11}){H9} |π(e) |ε|¬K|ur|)1|¬Ek|¬En|)|4|≤m(k)/k
5831 |g2|4α=↓|46/|≤p|g2|4α+↓|4O(1/n) (|πsee exercise
5834 4.5.2<10d); and |ε|¬K|ur|)1|¬Ek|¬En|)|4|≤m(k)|πlog
5837 |εk/k|g2|4α=↓|4O(1). |πHence |εh|βd(n)|4α=↓|4n(3|4|πln|42/|ε
5839 |≤p|g2)|4|πln|ε(n/d)|4α+↓|4O(n) |πfor |εd|4|¬R|41.
5842 |πSo |εh(n)|4α=↓|42|4|¬K|ur|)cd|¬Dn|)|4|≤m(d)h|βc(n/cd)|4α=↓
5843 |4{H11}({H9}(6|4|πln|42)/|ε|≤p|g2{H11}){H9}n(|πln|4|εn|4α_↓|
5843 4|¬K|4α_↓|4|¬K|¬S)|4α+↓|4O(n|≤s|βα_↓|β1(n)|g2{H11}){H9},
5844 |πwhere |ε|¬K|4α=↓|4|¬K|ur|)cd|¬Dn|)|4|≤m(d)|πln(|εcd)/cd|4α
5845 =↓|40 |πand |ε|¬K|¬S|4α=↓|4|¬K|ur|)cd|¬Dn|)|4|≤m(d)|πln
5848 |εc/cd|4α=↓|4|¬K|ur|)d|¬Dn|)|4|*/|≤!|\(d)/d. |π[It
5850 is well known that |ε|≤s|βα_↓|β1(n)|4α=↓|4O(|πlog|4log|4|εn)
5854 ; |πcf. Hardy and Wright, |εTheory of Numbers,
5862 |≤%22.9.]|'{A3}|π|≡3|≡5|≡.|4|9See ``Analysis
5865 of a subtractive algorithm,'' to appear.|'{H9L11M29}|≡3|≡6|≡
5871 .|4|9Working the algorithm backwards, we want
5877 to choose |εk|β1,|4.|4.|4.|4,|4k|βn|βα_↓|β1 |πso
5881 that |εu|βk|4|"o|4F|βk|m1|4.|4.|4.|4F|βk|mi|mα_↓|m1F|βk|mi|β
5882 α_↓|β1 {H11}({H9}|πmodulo gcd(|εu|βi|βα+↓|β1,|4.|4.|4.|4,|4u
5884 |βn{H11}){H9} |πfor |ε1|4|¬E|4|¬W|4n, |πwith
5888 |εu|βn|4α=↓|4F|βk|m1|4.|4.|4.|4F|βk|mn|mα_↓|m1
5889 |πa minimum, where the |εk'|πs are positive,
5896 |εk|β1|4|¬R|43, |πand |εk|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4k
5898 |βn|βα_↓|β1|4α=↓|4N|4α+↓|4n|4α_↓|41. |πThe solution
5901 is |εk|β2|4α=↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4k|βn|βα_↓|β1|4α=↓|42
5902 , u|βn|4α=↓|4F|βN|βα_↓|βn|βα+↓|β3. [|πSee |εCACM
5906 |≡1|≡3 (1970), 433<436, 447<448.]|'{A3}{H9L11M29}|π|≡3|≡7|≡.
5910 |4|9See |εProc. Amer. Math. Soc. |≡7 (1956),
5917 1014<1021; |πcf. exercise 6.1<18.|'{A3}|≡3|≡8|≡.|4|9Let
5922 |εm|4α=↓|4|"pn/|≤f|"P, |πso that |εm/n|4α=↓|4|≤f|gα_↓|g1|4α+
5925 ↓|4|≤e|4α=↓|4|"Cx|β1,|4x|β2,|4.|4.|4.|4|"C |πwhere
5927 |ε0|4|¬W|4|≤e|4|¬W|41/n. |πLet |εk |πbe minimal
5932 such that |εx|βk|4α=↓|42; |πthen {H11}({H9}|ε|≤f|g1|gα_↓|gk|
5936 4α+↓|4(|→α_↓1)|gkF|βk|βα_↓|β1|≤e{H11}){H9}/{H11}({H9}|≤f|gα_
5936 ↓|gk|4α_↓|4(|→α_↓1)|gkF|βk|≤e{H11}){H9}|4|¬R|42,
5937 |πhence |εk |πis even and |ε|≤f|gα_↓|g2|4α=↓|42|4α_↓|4|≤f|4|
5942 ¬E|4|≤f|gkF|βk|βα+↓|β2|≤e|4α=↓|4(|≤f|g2|gk|gα+↓|g2|4α_↓|4|≤f
5942 |gα_↓|g2)|≤e/|¬H|v45|). [Ann. Polon. Math. |≡1
5947 (1954), 203<206.]|'{A3}{H9L11M29}|π|≡3|≡9|≡.|4|9At
5950 least 287 at bats; |"C2, 1, 95|"C|4α=↓|496/287|4α=↓|4.334494
5956 77|4.|4.|4.|4, and no fraction with denominator
5962 |→|¬W287 lies in [.3335, .3345]|4α=↓|4[|"C2,
5967 1, 666|"C, |"C2, 1, 94, 1, 1, 3|"C].|'!!|1|1To
5976 solve the general question of the fraction in
5984 [9|εa, b] |πwith smallest denominator, where
5990 |ε0|4|¬W|4a|4|¬W|4b|4|¬W|41, |πnote that in terms
5995 of regular continued fraction representations
6000 we have |ε|"Cx|β1, x|β2,|4.|4.|4.|"C|4|¬W|4|"Cy|β1,
6004 y|β2,|4.|4.|4.|"C |πi= |ε(|→α_↓1)|gjy|βj |πfor
6008 the smmallest |εj |πwith |εx|βj|4|=|↔6α=↓|4y|βj,
6013 |πwhere we place ``|¬X'' after the last partial
6021 quotient of a rational number. Thus if |εa|4α=↓|4|"Cx|β1,
6029 x|β2,|4.|4.|4.|"C |πand |εb|4α=↓|4|"Cy|β1, y|β2,|4.|4.|4.|"C
6032 , |πthe fractions in |ε[a, b] |πhave the form
6041 |εc|4α=↓|4|"Cx|β1,|4.|4.|4.|4,|4x|βj|βα_↓|β1,
6042 z|βj,|4.|4.|4.|4,|4z|βm|"C |πwhere |ε|"Cz|βj,|4.|4.|4.|4,|4z
6044 |βm|"C |πlies between |ε|"Cx|βj, x|βj|βα+↓|β1,|4.|4.|4.|"C
6049 |πand |ε|"Cy|βj, y|βj|βα+↓|β1,|4.|4.|4.|"C |πinclusive.
6053 Let |εQ|βα_↓|β1|4α=↓|40. |πThe denominator |εQ|βj|βα_↓|β1(x|
6057 β1,|4.|4.|4.|4,|4x|βj|βα_↓|β1)Q|βm|βα_↓|βj|βα+↓|β1(z|βj,|4.|
6057 4.|4.|4,|4z|βm)|4α+↓|4Q|βj|βα_↓|β2(x|β1,|4.|4.|4.|4,|4x|βj|β
6057 α_↓|β2)Q|βm|βα_↓|βj(z|βj|βα+↓|β1,|4.|4.|4.|4,|4z|βm)
6058 |πof |εc |πis minimized when |εm|4α=↓|4j |πand
6065 |εz|βj|4α=↓|4(j |πodd|4|"M|4|εy|βj|4α+↓|41|4α_↓|4|≤d|βy|mj|m
6066 α+↓|m1|β|¬X; x|βj|4α+↓|41|4α_↓|4|≤d|βx|mj|mα+↓|m1|β|¬X).|'
folio 790 galley 10
6068 |H{U0}{H9L11M29}58320#Computer Programming(Knuth/A.-W.)!f.
6070 790!ch. 4!g. 10c|'{A24}{H10L12M29}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|9|
6073 ∨4|∨.|∨5|∨.|∨4|'{A12}{H9L11M29}|1|9|≡1|≡.|4|9If
6075 |εd|βk |πisn't prime, its prime factors are cost
6083 out before |εd|βk |πis tried.|'{A3}|9|1|≡2|≡.|4|9No,
6089 the alforithm would fail if |εp|βt|βα_↓|β1|4α=↓|4p|βt,
6095 |πgiving ``1'' as a spurious prime factor.|'{A3}|9|1|≡3|≡.|9
6102 |4Let |εP |πbe the product of the _rst 168 primes.
6112 (|εNote|*/: |π|\Although |εP |πis a large number,
6119 it is considerably faster on many computers to
6127 calculate this gcd than to do the 168 divisions,
6136 if we just want to test whether or not |εn |πis
6147 prime.)|'{A3}|1|9|≡4|≡.|4|9Cf. exercise 3.1<11
6151 and Eq. 4.5.3<21; the average is asymptotically
6158 |ε|≤p|g2/12 |πtimes the average value of |ε|≤m|4α+↓|4|≤l,
6165 |πsince |εn|4α=↓|4|≤l|≤d|β|≤m|β0|4α+↓|4|≤m|4α+↓|4|≤l|4α_↓|41
6166 |4α_↓|4{H11}({H9}(|≤m|4α+↓|4|≤l|4α_↓|41)|πmod|4|ε|≤l{H11}){H
6166 9}.|'{A3}{H9L11M29}|1|9|≡5|≡.|4|9x|4|πmod 3|4α=↓|40;
6169 |εx|4|πmod|45|4α=↓|40, 1, 4; |εx|4|πmod|47|4α=↓|40,
6173 1, 6; |εx|4|πmod|48|4α=↓|41, 3, 5, 7; |εx|4|¬Q|4103.
6180 |πThe _rst try is |εx|4α=↓|4105: (105)|g2|4α_↓|410541|4α=↓|4
6185 484|4α=↓|422|g2. |πThis would also have been
6191 found by Algorithm C in a relatively short time.
6200 Thus 10541|4α=↓|483|4|¬O|4127.|'{A3}|1|9|≡6|≡.|4|9Let
6203 us count the number of solutions |ε(x, y) |πof
6212 the congruence |εN|4|"o|4(x|4α_↓|4y)(x|4α+↓|4y)
6215 (|πmodulo |εp), |πwhere |ε0|4|¬E|4x, y|4|¬W|4p.
6220 |πSince |εN|4|=|↔6|"o|40 |πand |εp |πis prime,
6226 |εx|4α+↓|4y|4|=|↔6|"o|40. |πFor each |εv|4|=|↔6|"o|40
6230 |πthere is a unique |εu (|πmodulo |εp) |πsuch
6238 that |εN|4|"o|4uv. |πThe congruences |εx|4α_↓|4y|4|"o|4u,
6243 x|4α+↓|4y|4|"o|4v |πnow uniquely determine |εx
6248 |πmod |εp |πand |εy |πmod |εp, |πsince |εp |πis
6257 odd. Thus the stated congruence has exactly |εp|4α_↓|41
6265 |πsolutions (|εx,|4y). |πIf |ε(x,|4y) |πis a
6271 solution, so is |ε(x, p|4α_↓|4y) |πif |εy|4|=|↔6α=↓|40,
6278 |πsince (|εp|4α_↓|4y)|g2|4|"o|4y|g2; |πand if
6282 |ε(x, y|β1) |πand |ε(x, y|β2) |πare solutions
6289 with |εy|β1|4|=|↔6α=↓|4y|β2, |πwe have |εy|ur2|)1|)|4|"o|4y|
6293 ur2|)2|); |πhence |εy|β1|4α=↓|4p|4α_↓|4y|β2.
6296 |πThus the number of di=erent |εx |πvalues among
6304 the solutions |ε(x, y) |πis |ε(p|4α_↓|41)/2 |πif
6311 |εN|4|"o|4x|g2 |πhas no solutions, or |ε(p|4α+↓|41)/2
6317 |πif |εN|4|"o|4x|g2 |πhas solutions.|'{A3}|9|1|≡7|≡.|4|9One
6322 procedure is to keep two indices for each modulus,
6331 one for the current word position and one for
6340 the current bit position; loading two words of
6348 the table and doing an indexed shift command
6356 will bring the table entries into proper alignment.|'
6364 {A3}{H9L11M29}|1|9|≡8|≡.|4|9(We may assume that
6368 |εN|4α=↓|42M |πis even.) The following algorithm
6374 uses an auxiliary table |εX[1], X[2],|4.|4.|4.|4,|4X[M],
6380 |πwhere |εX[k] |πrepresents the primality of
6386 |ε2k|4α+↓|41.|'{A3}{I3H}|1|1!!|≡S|≡1|≡.|9|πSet
6388 |εX[k]|4|¬L|41 |πfor |ε1|4|¬E|4k|4|¬E|4M. |πAlso
6392 set |εj|4|¬L|41, p|4|¬L|41, p|4|¬L|43, q|4|¬L|44.
6397 (|πDuring this alforithm |εp|4α=↓|42j|4α+↓|41,
6401 q|4α=↓|42j|4α+↓|42j|g2; |πthe integer variables
6405 |εj, k, p, q |πmay readily be manipulated in
6414 index registers.)|'{A3}!!|1|1|≡S|≡2|≡.|9If |εX[j]|4α=↓|40,
6418 |πgo to S4. Otherwise output |εp, |πwhich is
6426 prime, and set |εk|4|¬L|4q.|'{A3}!!|1|1|π|≡S|≡3|≡.|9If
6431 |εk|4|¬E|4M, |πthen set |εX[k]|4|¬L|40, k|4|¬L|4k|4α+↓|4p,
6436 |πand repeat this step.|'{A3}|1|1!!|≡S|≡4|≡.|4|9Set
6441 |εj|4|¬L|4j|4α+↓|41, p|4|¬L|4p|4α+↓|42, q|4|¬L|4q|4α+↓|42p|4
6443 α_↓|42. |πIf |εj|4|¬E|4M, |πreturn to S2.|'{A3}{IC}{H9L11M29
6449 }A major part of this calculation could be made
6458 noticeably faster if |εq (|πinstead of |εj) |πwere
6466 tested against |εM |πin step S4, and if a new
6476 loop were appended which outputs |ε2j|4α+↓|41
6482 |πfor all remaining |εX[j] |πthat equal 1, suppressing
6490 the manipulation of |εp |πand |εq.|'{A3}|1|9|≡9|≡.|4|9|πIf
6497 |εp|g2 |πis a divisor of |εn |πfor some prime
6506 |εp, |πthen |εp |πis a divisor of |ε|≤l(n), |πbut
6515 not of |εn|4α_↓|41. |πIf |εn|4α=↓|4p|β1p|β2,
6520 |πwhere |εp|β1|4|¬W|4p|β2 |πare primes, then
6525 |εp|β2|4α_↓|41 |πis a divisor of |ε|≤l(n) |πand
6532 therefore |εp|β1p|β2|4α_↓|41|4|"o|40 {H11}({H9}|πmodulo
6535 (|εp|β2|4α_↓|41){H11}){H9}. |πSince |εp|β2|4|"o|41,
6538 p|β1|4α_↓|41 |πis a multiple of |εp|β2|4α_↓|41;
6544 |πbut this contradicts |εp|β1|4|¬W|4p|β2. {H11}({H9}|πValues
6548 of |εn |πfor which |ε|≤l(n) |πproperly divides
6556 |εn|4α_↓|41 |πare called ``Carmichael numbers.''
6561 See D. Shanks, |εSolved and Unsolved Problems
6568 in Number Theory |≡1 (|πWashington, D.C.: Spartan,
6575 1962), Sections 39<40.{H11}){H9}|'{A3}|≡1|≡0|≡.|4|9Let
6579 |εk|βp |πbe the order of |εx|βp |πmodulo |εn,
6587 |πand let |ε|≤l |πbe the least common multiple
6595 of all the |εk|βp'|πs. Then |ε|≤l |πis a divisor
6604 of |εn|4α_↓|41 |πbut not of any (|εn|4α_↓|41)/p,
6611 |πso |ε|≤l|4α=↓|4n|4α_↓|41. |πSince |εx|ur|≤'(n)|)p|)
6615 |πmod |εn|4α=↓|41, |≤'(n) |πis a multiple of
6622 |εk|βp |πfor all |εp, |πso |ε|≤'(n)|4|¬R|4|≤l.
6628 |πBut |ε|≤'(n)|4|¬W|4n|4α_↓|41 |πwhen |εn |πis
6633 not prime. (Another way to carry out the proof
6642 is to construct an element |εx |πof order |εn|4α_↓|41
6651 |πfrom the |εx|βp'|πs, by the method of exercise
6659 3.2.1.2<15.)|'{A3}|∂!!!|∂!!!|∂!!!|∂!!!!|∂!!|∂!!!|∂!!!!!!!|∂|
6660 E|;|≡1|≡1|≡.|E|'|>|εU|;V|;A|;P|;S|;T|;|πOutput|;
6670 >{A3}|>1984|4|4|?1|4|4|?0|4|4|?992|4|4|4|?0|4|4|4|?
6677 #|4|4|?|;>|>1981|4|4|?1981|4|4|?1|4|4|?992|4|4|4|?
6685 1|4|4|4|?1981|4|4|4|?|;>|>1983|4|4|?4|4|4|?495|4|4|?
6693 993|4|4|4|?0|4|4|4|?1|4|4|?993|g2|4|"o|42|g2|4|4|4|?
6697 >|>1983|4|4|?991|4|4|?2|4|4|?98109|4|4|4|?1|4|4|4|?
6704 |;>|>1981|4|4|?4|4|4|?495|4|4|?2|4|4|4|?0|4|4|4|?
6712 1|4|4|?2|g2|4|"o|42|g2|4|4|4|?>|>1984|4|4|?1981|4|4|?
6718 1|4|4|?99099|4|4|4|?1|4|4|4|?1981|4|4|?|;>|>1984|4|4|?
6726 1|4|4|?1984|4|4|?99101|4|4|4|?0|4|4|4|?1|4|4|?
6731 99101|g2|4|"o|42|g0|4|4|4|?>{A7}{H9L11M29}The
6734 factorization 199|4|¬O|4991 is evident from the
6740 _rst or last outputs. The shortness of the cycle,
6749 and the appearance of the well-known number 1984,
6757 are probably just coincidences.|'{A3}|≡1|≡2|≡.|4|9The
6762 following algorithm makes use of an auxiliary
6769 |ε(m|4α+↓|41)|4α⊗↓|4(m|4α+↓|41) |πmatrix of single-precision
6772 integers |εE|βj|βk, 0|4|¬E|4j, k|4|¬E|4m; |πa
6778 single-precision vector |ε(b|β0, b|β1,|4.|4.|4.|4,|4b|βm);
6782 |πand a multiple-precision vector |ε(x|β0, x|β1,|4.|4.|4.|4,
6787 |4x|βm) |πwith entries in the range |ε0|4|¬E|4x|βk|4|¬W|4N.|
6793 '{A3}{I3H}|π!!|1|1|≡F|≡1|≡.|9[Initialize.] Set
6796 |εb|βi|4|¬L|4|→α_↓1 |πfor |ε0|4|¬E|4i|4|¬E|4m;
6799 |πthen set |εj|4|¬L|40.|'!!|1|1|π|≡F|≡2|≡.|9[Next
6803 solution.] Get the next output (|εx, e|β0, e|β1,|4.|4.|4.|4,
6810 |4e|βm |πproduced by Algorithm E. (It is convenient
6818 to regard Algorithms E and F as coroutines.)
6826 Set |εk|4|¬L|40.|'!!|1|1|π|≡F|≡3|≡.|9[Search
6829 for odd.] If |εk|4|¬Q|4m |πgo to step F5. Otherwise
6838 if |εe|βk |πis even, set |εk|4|¬L|4k|4α+↓|41
6844 |πand repeat this step.|'!!|1|1|≡F|≡4|≡.|9[Linear
6849 dependence?] If |εb|βk|4|¬R|40, |πthen set |εi|4|¬L|4b|βk,
6855 x|4|¬L|4(x|βix)|πmod |εN, e|βr|4|¬L|4e|βr|4α+↓|4E|βi|βr
6858 |πfor |ε0|4|¬E|4r|4|¬E|4m; |πset |εk|4|¬L|4k|4α+↓|41
6862 |πand return to F3. Otherwise set |εb|βk|4|¬L|4j,
6869 x|βj|4|¬L|4x, E|βj|βr|4|¬L|4e|βr |πfor |ε0|4|¬E|4r|4|¬E|4m;
6873 |πset |εj|4|¬L|4j|4α+↓|41 |πand return to F2.
6879 (In the latter case we have a new linearly independent
6889 solution, modulo 2, whose _rst odd component
6896 is |εe|βk.)|'!!|1|1|π|≡F|≡5|≡.|9[Try to factor.]
6901 (Now |εe|β0, e|β1,|4.|4.|4.|4,|4e|βm |πare even.)
6906 Set|'{A8}|εy|4|¬L|4{H11}({H9}(|→α_↓1) |ge|r0|g/|g2p|ure|β1/2
6908 |)1|)|4.|4.|4.|4p|ure|βm/2|)m|){H11}){H9}|πmod|4|εN.|;
6909 {A7}|π!!!!|1If |εx|4α=↓|4y |πor if |εx|4α+↓|4y|4α=↓|4N,
6914 |πreturn to F2. Otherwise compute gcd(|εx|4α_↓|4y,
6920 N), |πwhich is a proper factor of |εN, |πand
6929 terminate the algorithm.|'{A3}{IC}{H9L11M29}It
6933 can be shown that this algorithm _nds a factor,
6942 whenever one is deducible from the given outputs
6950 of Algorithm E.|'{A3}|≡1|≡3|≡.|4|9|εf|1(p,|4p|g2d)|4α=↓|42/(
6953 p|4α+↓|41)|4α+↓|4f|1(p,|4d)/p, |πsince |ε1/(p|4α+↓|41)
6956 |πis the probability that |εA |πis a multiple
6964 of |εp. f|1(p,|4pd)|4α=↓|41/(p|4α+↓|41) |πwhen
6968 |εd|4|πmod|4|εp|4|=|↔6α=↓|40. f|1(2,|44k|4α+↓|43)|4α=↓|4|f1|
6969 d33|) |πsince |εA|g2|4α_↓|4(4k|4α+↓|43)B|g2 |πcannot
6973 be a multiple of 4; |εf|1(2,|48k|4α+↓|45)|4α=↓|4|f2|d33|)
6979 |πsince |εA|g2|4α_↓|4(8k|4α+↓|45)B|g2 |πcannot
6982 be a multiple of 8; |εf|1(2,|48k|4α+↓|41)|4α=↓|4|f1|d33|)|4α
6987 +↓|4|f1|d33|)|4α+↓|4|f1|d33|)|4α+↓|4|f1|d36|)|4α+↓|4|f1|d312
6987 |)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4|f4|d33|). f|1(p,|4d)|4α=↓|
6988 4(2p/(p|g2|4α_↓|41), 0{H11}){H9} |πif |εd|g(|gp|gα_↓|g1|g)|g
6991 /|g2 |πmod |εp|4α=↓|4(1,|4p|4α_↓|41), |πrespectively,
6995 for odd |εp.|'{A3}|π|≡1|≡4|≡.|4|9Since |εP|g2|4|"o|4kNQ|g2
7000 (|πmodulo |εp) |πfor any prime divisor |εp |πof
7008 |εV, |πwe have 1|4|"o|4|εP|ur2(pα_↓1)/2|)|)|4|"o|4(kNQ|g2)|u
7011 r(pα_↓1)/2|)|)|4|"o|4(kN)|ur(pα_↓1)/2|)|) (|πmodulo
7013 |εp), |πif |εP|4|=|↔6|"o|40.|'|H*?*?*?{U0}{H9L11M29}58320#Compu
folio 794 galley 11
7016 ter Programming!(Knuth/A.-W.)!f. 794!ch. 4!g.
7020 11c|'{A12}|π|≡1|≡5|≡.|4|9|εU|βn|4α=↓|4(a|gn|4α_↓|4b|gn)/|¬H|
7021 v4D|), |πwhere |εa|4α=↓|4|f1|d32|)(P|4α+↓|4|¬H|v4D|)),
7024 b|4α=↓|4|f1|d32|)(P|4α_↓|4|¬H|v4D|)), D|4α=↓|4P|g2|4α_↓|44Q.
7025 |πThen |ε2|gn|gα_↓|g1U|βn|4α=↓|4|¬K|βk(|fn|d52kα+↓1|))P|gn|
7027 gα_↓|g2|gk|gα_↓|g1D|gk; |πso |εU|βp|4|"o|4D|ur(pα_↓1)/2|)|)
7030 (|πmodulo |εp) |πif |εp |πis an odd prime. similarly,
7039 if |εV|βn|4α=↓|4a|gn|4α+↓|4b|gn|4α=↓|4U|βn|βα+↓|β1|4α_↓|4QU|
7040 βn|βα_↓|β1, |πthen |ε2|gn|gα_↓|g1V|βn|4α=↓|4|¬K|βk
7043 (|fn|d52k|))P|gn|gα_↓|g2|gkD|gk, |πand |εV|βp|4|"o|4P|gn|4|"
7045 o|4P. |πThus if |εU|βp|4|"o|4|→α_↓1, |πwe _nd
7051 that |εU|βp|βα+↓|β1 |πmod |εp|4α=↓|40. |πIf |εU|βp|4|"o|41,
7057 |πwe _nd that |ε(QU|βp|βα_↓|β1)|πmod |εp|4α=↓|40;
7062 |πhere if |εQ |πis a multiple of |εp, U|βn|4|"o|4P|gn|gα_↓|g
7070 1 (|πmodulo |εp) |πfor |εn|4|¬Q|40, |πso |εU|βn
7077 |πis never a multiple of |εp; |πif |εQ |πis not
7087 a multiple of |εp, U|βp|βα_↓|β1 |πmod |εp|4α=↓|40.
7094 |πTherefore as in Theorem L, |εU|βt |πmod |εN|4α=↓|40
7102 |πif |εN|4α=↓|4p|ure|β1|)1|)|4.|4.|4.|4p|ure|βr|)r|),
7104 |πgcd(|εN, Q)|4α=↓|41, |πand |εt|4α=↓|4|πlcm|ur|)1|¬Ej|¬Er|)
7107 {H11}({H9}p|ure|βjα_↓1|)j|)(p|βj|4α+↓|4|≤e|βj){H11}){H9}.
7108 |πUnder the assumptions of this exercise, the
7115 rank of apparition of |εN |πis |εN|4α+↓|41; |πhence
7123 |εN |πis prime to |εQ |πand |εt |πis a multiple
7133 of |εN|4α+↓|41. |πAlso, the assumptions of this
7140 exercise imply that each |εp|βj |πis odd and
7148 each |ε|≤e|βj |πis |→|¬N1, so |εt|4|¬E|42|g1|gα_↓|gr|4|≥7p|u
7153 re|βjα_↓1|)j|)(p|βj|4α+↓|4|f1|d33|)p|βj)|4α=↓|42(|f2|d33|))|
7153 grN; |πhence |εr|4α=↓|41 |πand |εt|4α=↓|4p|ure|β1|)1|)|4α+↓|
7157 4|≤e|β1p|ure|β1α_↓1|)1|). |πFinally, therefore
7160 |εe|β1|4α=↓|41 |πand |ε|≤e|β1|4α=↓|41.|'!!|1|1Note|*/:
7164 |\|πObviously if this test for primality is to
7172 be any good, we must choose |εP |πand |εQ |πin
7182 some way which makes it likely that the test
7191 will work. Lehmer suggests taking |εP|4α=↓|41
7197 |πso that |εD|4α=↓|41|4α_↓|44Q, |πand choosing
7202 |εQ |πsi that gcd(|εN, QD)|4α=↓|41. (|πIf the
7209 latter condition fails, we know already that
7216 |εN |πis not prime, unless |ε|¬GQ|¬G|4|¬R|4N.)
7222 |πFurthermore, the derivation above shows that
7228 we will want |ε|≤e|β1|4α=↓|41, |πthat is, |εD|ur(Nα_↓1)/2|)|
7234 )|4|"o|4|→α_↓1 (|πmodulo |εN). |πThis is another
7240 condition which determines the choice of |εQ.
7247 |πFurthermore, if |εD |πsatis_es this condition,
7253 and if |εU|βN|βα+↓|β1 |πmod |εN|4|=|↔6α=↓|40,
7258 |πwe know that |εN |πis |εnot |πprime.|'!!|1|1|εExample|*/:
7266 |\|πIf |εP|4α=↓|41, Q|4α=↓|4|→α_↓1, |πwe have
7271 the Fibonacci sequence, with |εD|4α=↓|45. |πSince
7277 5|g1|g1|4|"o|4|→α_↓1 (modulo 23), we might attempt
7283 to prove that 23 is prime by using the Fibonacci
7293 sequence:|'{A8}|ε|↔bF|βn |πmod 23|↔v|4α=↓|40,
7297 1, 1, 2, 3, 5, 8, 13, 21, 11, 9, 20, 6, 3, 9,
7311 12, 21, 10, 8, 18, 3, 21, 1, 22, 0, . . .|;{A9}{H9L11M29}so
7325 24 is the rank of apparition of 23 and the test
7336 works. However, the Fibonacci sequence cannot
7342 be used in this way to prove the primality of
7352 13 or 17, since |εF|β7 |πmod 13|4α=↓|40 |πand
7360 |εF|β9 |πmod 17|4α=↓|40. When |εp|4|"o|4|→|¬N1
7365 (|πmodulo 10), we have 5|ur|ε(pα_↓1)/2|)|) |πmod
7371 |εp|4α=↓|41, |πso |εF|βp|βα_↓|β1 |π(not |εF|βp|βα+↓|β1)
7376 |πis divisible by |εp.|'{A3}|π|≡1|≡3|≡.|4|9Let
7381 |εf|1(q)|4α=↓|42|4|πlg|4|εq|4α_↓|41. |πWhen |εq|4α=↓|42
7384 |πor 3, the tree has at most |εf|1(q) |πnodes.
7393 When |εq|4|¬Q|43 |πis prime, let |εq|4α=↓|41|4α+↓|4q|β1|β1|4
7398 .|4.|4.|4q|βt |πwhere |εt|4|¬R|42 |πand |εq|β1,|4.|4.|4.|4,|
7402 4q|βt |πare prime. The size of the tree is |ε|→|¬E1|4α+↓|4|¬
7411 K|4f(q|βk)|4α=↓|42|4α+↓|4f|1(q|4α_↓|41)|4α_↓|4t|4|¬W|4f|1(q)
7411 . [Siam J. Comp. |≡7 (1975), 214<220.]|'{A3}|≡1|≡8|≡.|4|9|εx
7418 {H11}({H9}G(|≤a)|4α_↓|4F(|≤a){H11}){H9} |πis
7420 the number of |εn|4|¬E|4x |πwhose second-largest
7426 prime factor is |→|¬E|εx|g|≤a |πand whose largest
7433 prime factor is |ε|→|¬Qx|g|≤a. |πHence |εxG|¬S(t)|4dt|4α=↓|4
7438 {H11}({H9}|≤p(x|gt|gα+↓|gd|gt)|4α_↓|4|≤p(x|gt){H11}){H9}.
7439 x|g1|gα_↓|gt{H11}({H9}G(t/(1|4α_↓|4t){H11}){H9}|4α_↓|4F{H11}
7439 ({H9}t/(1|4α_↓|4t)){H11}){H9}. |πThe probability
7442 that |εp|βt|βα_↓|β1|4|¬E|4|¬H|v4p|βt|) |πis |¬J|ur1|)0|)|4|ε
7445 F{H11}({H9}t/2(1|4α_↓|4t){H11}){H9}t|gα_↓|g1|4dt.
7446 [|πNumerical evaluation yields .62433. Curiously,
7451 it can be shown that this also equals |ε|¬J|ur1|)0|)|4F{H11}
7459 ({H9}t/(1|4α_↓|4t){H11}){H9}|4dt, |πthe average
7462 value of log |εp|βt/|πlog |εx. |πThe derivative
7469 |εG|¬S(0) |πcan be shown to equal |ε|¬J|ur1|)0|)|4F{H11}({H9
7475 }t/(1|4α_↓|4t){H11}){H9}t|gα_↓|g2|4dt|4α=↓|4F(1)|4α+↓|42F(|f
7475 1|d32|))|4α+↓|43F(|f1|d33|))|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|41
7475 .78107. |πThe third-largest prime factor has
7481 |εH(|≤g)|4α=↓|4|¬J|ur|≤g|)0|)|4{H11}({H9}H(t/(1|4α_↓|4t))|4α
7481 _↓|4G(t/(1|4α_↓|4t)){H11}){H9}t|gα_↓|g1|4dt |πand
7483 |εH|¬S(0)|4α=↓|4|¬X. |πSee D. E. Knuth and L.
7490 Trabb-Pardo, to appear.]|'{A3}|≡1|≡9|≡.|4|9|εM|4α=↓|42|gD|4α
7493 _↓|41 |πis a multiple of all |εp |πfor which
7502 the order of 2 modulo |εp |πdivides |εD. |πLet
7511 |εa|β1|4α=↓|42 |πand |εa|βj|βα+↓|β1|4α=↓|4a|urq|βj|)j|)
7514 |πmod |εN, |πwhere |εq|βj|4α=↓|4p|ure|βj|)j|),
7518 p|βj |πis the |εj|πth prime, and |εe|βj|4α=↓|4|"l|πlog|41000
7524 /log|4|εp|βj|"L; |πlet |εA|4α=↓|4a|β1|β6|β9.
7527 |πNow compute |εb|βq|4α=↓|4|πgcd(|εA|gq|4α_↓|41,
7530 N) |πfor all primes |εq |πbetween 10|g3 and 10|g5.
7539 One way to do this is to start with |εA|g1|g0|g0|g9
7549 |πmod |εN |πand then to multiply alternately
7556 by |εA|g4 |πmod |εN |πand |εA|g2 |πmod |εN. (|πA
7565 similar method was used in the 1920's by D. N.
7575 Lehmer, but he didn't publish it.) As with Algorithm
7584 B we can avoid most of the gcd's by batching;
7594 e.g., since |εb|β3|β0|βα_↓|βk|4α=↓|4|πgcd(|εA|g3|g0|gr|4α_↓|
7596 4A|gk, N) |πwe might try batches of 8, computing
7605 |εc|βr|4α=↓|4(A|g3|g0|gr|4α_↓|4A|g2|g9)(A|g3|g0|gr|4α_↓|4A|g
7605 2|g3)|4.|4.|4.|4(A|g3|g0|gr|4α_↓|4A) |πmod |εN,
7608 |πthen gcd(|εc|βr, N) |πfor 33|4|¬W|4|εr|4|¬E|43334.|'
7613 {A24}{H10L12M29}|π|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|4|∨4|∨.|∨6|'
7614 {A12}{H9L11M29}|1|9|≡1|≡.|4|9|ε9x|g2|4α+↓|47x|4α+↓|49;
7615 5x|g3|4α+↓|47x|g2|4α+↓|42x|4α+↓|46.|'{A3}|1|9|≡2|≡.|4|9|π(a)
7616 True. (b) False if the algebraic system |εS
7625 |πcontains ``zero divisors'', nonzero numbers
7630 whose product is zero, as in exercise 1; otherwise
7639 true. (c) False; (|εx|4α+↓|41)|4α+↓|4{H11}({H9}(|→α_↓1)x|4α+
7642 ↓|40{H11}){H9}|4α=↓|41.|'{A3}{H9L11M29}|1|9|≡3|≡.|4|9|πAssum
7643 e that |εr|4|¬E|4s. |πFor |ε0|4|¬E|4k|4|¬E|4r
7648 |πthe maximum is |εm|β1m|β2(k|4α+↓|41); |πfor
7653 |εr|4|¬E|4k|4|¬E|4s |πit is |εm|β1m|β2(r|4α+↓|41);
7657 |πfor |εs|4|¬E|4k|4|¬E|4r|4α+↓|4s |πit is |εm|β1m|β2(r|4α+↓|
7661 4s|4α+↓|41|4α_↓|4k). |πThe least upper bound
7666 valid for all |εk |πis |εm|β1m|β2(r|4α+↓|41).
7672 (|πThe solver of this exercise will know how
7680 to factor the polynomial |εx|g7|4α+↓|42x|g6|4α+↓|43x|g5|4α+↓
7684 |43x|g4|4α+↓|43x|g3|4α+↓|43x|g2|4α+↓|42x|4α+↓|41.)|'
7685 {A3}|1|9|≡4|≡.|4|9|πIf the polynomials each have
7690 less than 2|ε|gt |πnonzero coe∃cients, the product
7697 can be formed by putting exactly |εt|4α_↓|41
7704 |πzeros between each of the coe∃cients, then
7711 multiplying in the binary number system, and
7718 _nally using a logical |¬a|¬n|¬d operation (present
7725 on most binary computers, cf. Section 4.5.4)
7732 to zero out the extra bits. For example if |εt|4α=↓|43,
7742 |πthe multiplication in the text would become
7749 (1001000001)|β2|4α⊗↓|4(1000001001)|β2 α=↓ (100-00-0--00-00-0
7751 0-)|β2; |πif we |¬a|¬n|¬d the result with the
7759 constant (1001001|4.|4.|4.|41001)|β2, the desired
7763 answer is obtained. A similar technique can be
7771 used to multiply polynomials with nonnegative
7777 coe∃cients when it is known that the coe∃cients
7785 will not be too large.|'{A3}|1|9|≡5|≡.|4|9Polynomials
7791 of degree |ε|→|¬E2n |πcan be represented as |εU|β1(x)x|gn|4α
7798 +↓|4U|β0(x) |πwhere deg (|εU|β1), |πdeg |ε(U|β0)|4|¬E|4n;
7804 |πand |ε{H11}({H9}U|β1(x)x|gn|4α+↓|4U|β0(x){H11})({H9}V|β1(x
7805 )x|gn|4α+↓|4V|β0(x){H11}){H9}|4α=↓|4U|β1(x)V|β1(x)(x|g2|gn|4
7805 α+↓|4x|gn)|4α+↓|4{H11}({H9}U|β1(x)|4α+↓|4U|β0(x){H11})({H9}V
7805 |β1(x)|4α+↓|4V|β0(x){H11}){H9}x|gn|4α+↓|4U|β0(x)V|β0(x)(x|gn
7805 |4α+↓|41). (|πThis equation assumes that arithmetic
7811 is being done modulo 2.) Thus Eqs. 4.3.3<3, 4,
7820 5 hold.|'|ε!!|1|1Note|*/: |\|πS. A. Cook has shown
7828 that Algorithm 4.3.3C can be extended in a similar
7837 way, and exercise 4.6.4<14 describes a method
7844 requiring even fewer operations for large |εn.
7851 |πBut these ideas are not useful for ``sparse''
7859 polynomials (having mostly zero coe∃cients).|'
7864 {A24}{H10L12M29}|∨S|∨E|∨C|∨T|∨I|∨O|∨N|4|4|4|∨4|∨.|∨6|∨.|∨1|'
7865 {A12}{H9L11M29}|1|9|≡1|≡.|4|9|εQ(X)|4α=↓|41|4|¬O|42|g3x|g3|4
7865 α+↓|40|4|¬O|42|g2x|g2|4α_↓|42|4|¬O|42x|4α+↓|48|4α=↓|48x|g3|4
7865 α_↓|44x|4α+↓|48; r(x)|4α=↓|428x|g2|4α+↓|44x|4α+↓|48.|'
7867 {A3}|π|1|9|≡2|≡.|4|9The monic sequence of polynomials
7872 produced during Euclid's algorithm has the coe∃cients
7879 (1, 5, 6, 6, 1, 6, 3), (1, 2, 5, 2, 2, 4, 5),
7893 (1, 5, 6, 2, 3, 4), (1, 3, 4, 6), 0. Hence the
7906 greatest common divisor is |εx|g3|4α+↓|43x|g2|4α+↓|44x|4α+↓|
7910 46. |π(The greatest common divisor of a polynomial
7918 and its reverse is always symmetric, in the sense
7927 that it is a unit multiple of its own reverse.)|'
7937 {A3}|1|9|≡3|≡.|4|9The procedure of Algorithm
7941 4.5.2X is valid, with polynomials over |εS |πsubstituted
7949 for integers. When the algorithm terminates,
7955 we have |εU(x)|4α=↓|4u|β2(x), V(x)|4α=↓|4u|β1(x).
7959 |πLet |εm|4α=↓|4|πdeg|ε(u), n|4α=↓|4|πdeg|ε(v).
7962 |πIt is easy to prove by induction that deg(|εu|β3)|4α+↓|4|π
7970 deg(|εv|β1)|4α=↓|4n, |πdeg|ε(u|β3)|4α+↓|4|πdeg|ε(v|β2)|4α=↓|
7971 4m, |πafter step X3, throughout the execution
7978 of the algorithm, provided that |εm|4|¬R|4n.
7984 |πHence if |εm |πand |εn |πare greater than |εd|4α=↓|4|πdeg{
7992 H11}({H9}gcd(|εu,|4v){H11}){H9} |πwe have deg(|εU)|4|¬W|4m|4
7995 α_↓|4d, |πdeg(|εV)|4|¬W|4n|4α_↓|4d; |πthe exact
7999 degrees are |εm|4α_↓|4d|β1 |πand |εn|4α_↓|4d|β1,
8004 |πwhere |εd|β1 |πis the degree of the second-last
8012 nonzero remainder. If |εd|4α=↓|4|πmin|ε(m, n),
8017 |πsay |εd|4α=↓|4n, |πwe have |εU(x)|4α=↓|40,
8022 V(x)|4α=↓|41.|'|π!!|1|1When |εu(x)|4α=↓|4x|gm|4α_↓|41
8025 |πand |εv(x)|4α=↓|4x|gn|4α_↓|41, |πthe identity
8029 |ε(x|gm|4α_↓|41)|πmod|ε(x|gn|4α_↓|41)|4α=↓|4x|gm|1|1|π|gm|go
8029 |gd|1|1|ε|gn|4α_↓|41 |πshows that all polynomials
8034 occurring during the calculation are monic with
8041 integer coe∃cients. When |εu(x)|4α=↓|4x|g2|g1|4α_↓|41,
8045 v(x)|4α=↓|4x|g1|g3|4α_↓|41, |πwe have |εV(x)|4α=↓|4(x|g1|g1|
8048 4α+↓|4x|g8|4α+↓|4x|g6|4α+↓|4x|g3|4α+↓|41), U(x)|4α=↓|4|→α_↓(
8049 x|g1|g9|4α+↓|4x|g1|g6|4α+↓|4x|g1|g4|4α+↓|4x|g1|g1|4α+↓|4x|g8
8049 |4α+↓|4x|g6|4α+↓|4x|g3|4α+↓|4x). |π[See also
8052 Eq. 3.3.3<29, which gives an alternative formula
8059 for |εU(x), V(x).]|'|H*?*?{U0}{H9L11M29}58320#Computer
folio 797 galley 12
8063 Programming!(Knuth/A.-W.)!f. 797!ch. 4!g 12c|'
8067 {A12}|π|1|9|≡4|≡.|9|4Since the quotient |εq(x)
8071 |πdepends only on |εv(x) |πand the _rst |εm|4α_↓|4n
8079 |πcoe∃cients of |εu(x), |πthe remainder |εr(x)|4α=↓|4u(x)|4α
8084 _↓|4q(x)v(x) |πis uniformly distributed and independent
8090 of |εv(x). |πHence each step of the algorithm
8098 may be regarded as independent of the others;
8106 this algorithm is much more well-behaved than
8113 Euclid's algorithm over the integers.|'!!|1|1The
8119 probability that |εn|β1|4α=↓|4n|4α_↓|4k |πis
8123 |εp|g1|gα_↓|gk(1|4α_↓|41/p), |πand |εt|4α=↓|40
8126 |πwith probability |εp|gα_↓|gn. |πEach succeeding
8131 step has essentially the same behavior; hence
8138 we can see that any given sequence of degrees
8147 |εn, n|β1,|4.|4.|4.|4,|4n|βt, |→α_↓|¬X |πoccurs
8151 with probability |ε(p|4α_↓|41)|gt/p|gn. |πTo
8155 _nd the average value of |εf|1(n|β1,|4.|4.|4.|4,|4n|βt),
8161 |πlet |εS|βt |πbe the sum of |εf|1(n|β1,|4.|4.|4.|4,|4n|βt)
8168 |πover all sequences |εn|4|¬Q|4n|β1|4|¬Q|1|1|¬O|4|¬O|4|¬O|1|
8171 1|¬Q|4n|βt|4|¬R|40 |πhaving a given value of
8177 |εt; |πthen the average is |ε|¬K|βt|4S|βt(p|4α_↓|41)|gt/p|gn
8182 .|'{H9L11M29}!!|1|1Let |εf|1(n|β1,|4.|4.|4.|4,|4n|βt)|4α=↓|4
8184 t; |πthen |εS|βt|4α=↓|4(|urn|)t|))(t|4α+↓|41),
8187 |πso the average is |εn(1|4α_↓|41/p). |πSimilarly,
8193 if |εf|1(n|β1,|4.|4.|4.|4,|4n|βt)|4α=↓|4n|β1|4α+↓|1|1|¬O|4|¬
8194 O|4|¬O|1|1α+↓|4n|βt, |πthen |εS|βt|4α=↓|4(|urn|)2|))(|urnα_↓
8196 1|)tα_↓1|)), |πand the average is |ε(|urn|)2|))(1|4α_↓|41/p)
8201 . |πFinally, if |εf|1(n|β1,|4.|4.|4.|4,|4n|βt)|4α=↓|4(n|4α_↓
8204 |4n|β1)n|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4(n|βt|βα_↓|β1|4α_↓
8204 |4n|βt)n|βt |πthen |εS|βt|4α=↓|4(|urnα+↓2|)tα+↓2|))|4α_↓|4(n
8206 |4α+↓|41)(|urnα+↓1|)tα+↓1|))|4α+↓|4(|urnα+↓1|)|92|))(|urn|)t
8206 |)), |πand the average is (|ε|urnα+↓1|)|92|))|4α_↓|4(n|4α+↓|
8211 41)p/(p|4α_↓|41)|4α+↓|4{H11}({H9}p/(p|4α_↓|41){H11}){H9}|g2(
8211 1|4α_↓|41/p|gn|gα+↓|g1).|'|π!!|1|1As a consequence
8215 we can see that if |εp |πis large there is very
8226 high probability that |εn|βj|βα+↓|β1|4α=↓|4n|βj|4α_↓|41
8230 |πfor all |εj. |π(If this condition fails over
8238 the rational numbers, it fails for all |εp, |πso
8247 we have further evidence for the text's claim
8255 that Algorithm C almost always _nds |εt|β3|4α=↓|1|1|¬O|4|¬O|
8261 4|¬O|1|1α=↓|42.)|'{U0}{H9L11M29}{A3}|π|1|9|≡5|≡.|4|9Using
8263 the formulas developed in exercise 4, with |εf|1(n|β1,|4.|4.
8270 |4.|4,|4n|βt)|4α=↓|4|≤d|βn|mt|β0, |πwe _nd the
8274 probability is |ε1|4α_↓|41/p |πif |εn|4|¬Q|40,
8279 1 |πif |εn|4α=↓|40.|'{A3}|π|1|9|≡6|≡.|4|9Assuming
8283 that the constant terms |εu(0) |πand |εv(0) |πare
8291 nonzero, imagine a ``right-to-left'' division
8296 algorithm, |εu(x)|4α=↓|4v(x)q(x)|4α+↓|4x|gm|gα_↓|gnr(x),
8298 |πdeg|ε(r)|4|¬W|4|πdeg|ε(v). |πWe obtain a gcd
8303 algorithm anlogous to Algorithm 4.5.2B, which
8309 is essentially Euclid's algorithm applied to
8315 the ``reverse'' of the original inputs (cf. exercise
8323 2), afterwards reversing the answer and multiplying
8330 by an appropriate power of |εx.|'{A3}|π|1|9|≡7|≡.|4|9The
8337 units of |εS |π(as polynomials of degree zero).|'
8345 {A3}|1|9|≡8|≡.|4|9If |εu(x)|4α=↓|4v(x)w(x), |πwhere
8348 |εu(x) |πhas integer coe∃cients while |εv(x)
8354 |πand |εw(x) |πhave rational coe∃cients, there
8360 are integers |εm |πand |εn |πsuch that |εm|4|¬0|4v(x)
8368 |πand |εn|4|¬O|4w(x) |πhave integer coe∃cients.
8373 Now |εu(x) |πis primitive, so we have|'{A9}|εu(x)|4α=↓|4|¬N|
8380 πPP{H11}({H9}|εm|4|¬0|4v(x){H11}){H9}|πpp{H11}({H9}|εn|4|¬O|
8380 4w(x){H11}){H9}.|;{A9}|π|9|1|≡9|≡.|4|9We can
8383 extend Algorithm E as follows: Let {H11}({H9}|εu|β1(x),
8390 u|β2(x), u|β3, u|β4(x){H11}){H9} |πand {H11}({H9}|εv|β1(x),
8395 v|β2(x), v|β3, v|β4(x){H11}){H9}|πbe quadruples
8399 satisfying the relations |εu|β1(x)u(x)|4α+↓|4u|β2(x)v(x)|4α=
8402 ↓|4u|β3u|β4(x), v|β1(x)u(x)|4α+↓|4v|β2(x)v(x)|4α=↓|4v|β3v|β4
8403 (x). |πThe extended algorithm starts with {H11}({H9}1,
8410 0, cont|ε(u), |πpp(|εu(x)){H11}){H9} |πand {H11}({H9}0,
8415 1, cont(|εv), |πpp|ε(v(x)){H11}){H9} |πand manipulates
8420 these quadruples in such a way as to preserve
8429 the above conditions, where |εu|β4(x), v|β4(x)
8435 |πrun through the same sequence as |εu(x), v(x)
8443 |πdo in Algorithm E. If |εau|β4(x)|4α=↓|4q(x)v|β4(x)|4α+↓|4b
8448 r(x), |πwe have |εav|β3{H11}({H9}u|β1(x), u|β2(x){H11}){H9}|
8452 4α_↓|4q(x)u|β3{H11}({H9}v|β1(x), v|β2(x){H11}){H9}|4α=↓|4{H1
8453 1}({H9}r|β1(x), r|β2(x){H11}){H9}, |πwhere |εr|β1(x)u(x)|4α+
8456 ↓|4r|β2(x)v(x)|4α=↓|4bu|β3v|β3r(x), |πso the
8459 extended algorithm can preserve the desired relations.
8466 If |εu(x) |πand |εv(x) |πare relatively prime,
8473 the extended algorithm eventually _nds |εr(x)
8479 |πof degree zero, and we obtain |εU(x)|4α=↓|4r|β2(x),
8486 V(x)|4α=↓|4r|β1(x) |πas desired. (In practice
8491 we would divide |εr|β1(x), r|β2(x), |πand |εbu|β3v|β3
8498 |πby gcd{H11}({H9}cont|ε(r|β1), |πcont(|εr|β2)).{H11}){H9}
8501 |πConversely, if such |εU(x) |πand |εV(x) |πexist,
8508 then |εu(x) |πand |εv(x) |πhave no common prime
8516 divisors, since they are primitive and have no
8524 common divisors of positive degree.|'{A3}{H9L11M29}|≡1|≡0|≡.
8529 |4|9By successively factoring polynomials which
8534 are reducible into polynomials of smaller degree,
8541 we must obtain a _nite factorization of any polynomial
8550 into irreducibles. The factorization of the |εcontent
8557 |πis unique. To show that there is at most one
8567 factorization of the primitive part, the key
8574 result is to prove that if |εu(x) |πis an irreducible
8584 factor of |εv(x)w(x), |πbut not a unit multiple
8592 of the irreducible polynomial |εv(x), |πthen
8598 |εu(x) |πis a factor of |εw(x). |πThis can be
8607 proved by observing that |εu(x) |πis a factor
8615 of |εv(x)w(x)U(x)|4α=↓|4rw(x)|4α_↓|4w(x)u(x)V(x)
8617 |πby the result of exercise 9, where |εr |πis
8626 a nonzero constant.|'{A3}{H9L11M29}|≡1|≡1|≡.|4|9The
8630 only row names needed to show that |εu|β4(x)
8638 |πhas integer coe∃cients are |εA|β1, A|β0, B|β4,
8645 B|β3, B|β2, B|β1, B|β0, C|β1, C|β0, D|β0. |πIn
8653 general, let |εu|βj|βα+↓|β2(x)|4α=↓|40; |πthen
8657 the rows needed for the proof are |εA|βn|m2|βα_↓|βn|mj
8665 |πthrough |εA|β0, C|βn|m2|βα_↓|βn|mj |πthrough
8669 |εC|β0, D|βn|m3|βα_↓|βn|mj |πthrough |εD|β0,
8673 |πetc.|'{A3}|≡1|≡2|≡.|4|9If |εn|βk|4α=↓|40, |πthe
8677 argument in the text can be modi_ed to show that
8687 the absolute value of the determinant is |ε|λ3|urn|βk|βα_↓|β
8694 1|)k|)/|≥7|ur|)1|¬Wj|¬Wk|)|4|λ3|ur(t|βjα_↓1)(t|βj|βα+↓|β1α_↓
8694 2)|)j|). |πIf the polynomials have a factor of
8702 positive degree, we can arti_cially assume that
8709 the polynomial zero has degree zero and use the
8718 above formula for |ε|λ3|βk|4α=↓|40. Note|*/: |\|πThe
8724 value |εR(u,|4v) |πof Sylvester's determinant
8729 is called the |εresultant |πof |εu |πand |εv,
8737 |πand the quantity (|→α_↓1)|urdeg|ε(u)(|πdeg(|εu)α_↓1)/2|)|)
8740 |4|λ3(u)|gα_↓|g1R(u,|4u|¬S) |πis called the |εdiscriminant
8745 |πof |εu. |πIf |εu(x)|4α=↓|4a(x|4α_↓|4|≤a|β1)|4.|4.|4.|4(x|4
8748 α_↓|4|≤a|βm) |πand |εv(x)|4α=↓|4b(x|4α_↓|4|≤b|β1)|4.|4.|4.|4
8750 (x|4α_↓|4|≤b|βn), |πwe have |εR(u,|4v)|4α=↓|4a|gnv(|≤a|β1)|4
8753 .|4.|4.|4v(|≤a|βm)|4α=↓|4(|→α_↓1)|gm|gnb|gmu(|≤b|β1)|4.|4.|4
8753 .|4u(|≤b|βn)|4α=↓|4a|gnb|gm|4|≥7|ur|)1|¬Ei|¬Em,1|¬Ej|¬En|)(|
8753 ≤a|βi|4α_↓|4|≤b|βj). |πIt follows that the polynomials
8759 of degree |εmn |πin |εy |πde_ned as the respective
8768 resultants of |εu(y|4α_↓|4x), u(y|4α+↓|4x), x|gmu(y/x),
8773 |πand |εu(yx) |πwith |εv(x) |πhave as respective
8780 roots the sums |ε|≤a|βi|4α+↓|4|≤b|βj, |πdi=erences
8785 |ε|≤a|βi|4α_↓|4|≤b|βj, |πproducts |ε|≤a|βi|≤b|βj,
8788 |πand quotients |ε|≤a|βi/|≤b|βj {H11}({H9}|πwhen
8792 |εv(0)|4|=|↔6α=↓|40{H11}){H9}. |πThis idea has
8796 been used by R. G. K. Loos to construct algorithms
8806 for arithmetic on algebraic numbers [|εSIAM J.
8813 Computing |≡5 (1976), |πto appear].|'!!|1|1If
8819 we replace each row |εA|βi |πin Sylvester's matrix
8827 by|'{A8}|ε(b|β0A|βi|4α+↓|4b|β1A|βi|βα+↓|β1|4α+↓|1|1|¬O|4|¬O|
8828 4|¬O|1|1α+↓|4b|βn|m2|βα_↓|β1|βα_↓|βiA|βn|m2|βα_↓|β1)
8829 α_↓ (a|β0B|βi α+↓ a|β1B|βi|βα+↓|β1 α+↓ |¬O |¬O
8836 |¬O α+↓ a|βn|m2|βα_↓|β1|βα_↓|βiB|βn|m2|βα_↓|β1),|;
8839 {A9}|π{H9L11M29}and then delete rows B|βn|m2|βα_↓|β1
8844 |πthrough |εB|β0 |πand the last |εn|β2 |πcolumns,
8851 we obtain an |εn|β1|4α⊗↓|4n|β1 |πdeterminant
8856 for the resultant instead of the original |ε(n|β1|4α+↓|4n|β2
8863 )|4α⊗↓|4(n|β1|4α+↓|4n|β2) |πdeterminant. In some
8867 cases the resultant can be evaluated e∃ciently
8874 by means of this determinant; see |εCACM |≡1|≡2
8882 (1969), 23<30, 302<303.|'{A3}{H9L11M29}|π|≡1|≡3|≡.|4|9If
8886 |ε|λ3|urt|βk|)k|)u|βk|βα_↓|β1(x)|4α=↓|4u|βk(x)q|βk|βα_↓|β1(x
8886 )|4α+↓|4|λ3|urt|βk|βα_↓|β1|)kα_↓1|)u|βk|βα+↓|β1(x)
8887 |πthen (|ε|λ3|βk|λ3|gx|r|gα+↓|g1)|gt|rk|λl|urx|βk|βα_↓|β1|)|
8888 )w(x)u|βk|βα_↓|β1(x)|4α=↓|4|λ3|gx|rkw(x)u|βk(x)|λ3|gy|rkq(x)
8888 |4α+↓|4(|λ3|βk|βα_↓|β1|λ3|urx|βk|βα_↓|β1α+↓1|)|))|urt|βk|βα_
8888 ↓|β1|)|)|λ3|urx|βk|βα+↓|β1|)|)w(x)u|βk|βα+↓|β1(x);
8889 |πso the new |εu|βk(x) |πis |ε|λ3|urx|βk|)|)w(x)u|βk(x),
8895 |πwhere |εx|β1|4α=↓|4x|β2|4α=↓|4t|β1|4α=↓|40,
8897 x|βk|βα+↓|β1|4α=↓|4x|βkt|βk|4α_↓|4x|βk|βα_↓|β1(t|βk|βα_↓|β1|
8897 4α_↓|41)|4α+↓|4t|βk|4α_↓|4t|βk|βα_↓|β1.|'{A3}|π|≡1|≡4|≡.|4|9
8898 Let |εp |πbe a prime of the domain, and let |εj,k
8909 |πbe maximum such that |εp|gk|¬Dv|βn|4α=↓|4|λ3(v),
8914 p|gj|¬Dv|βn|βα_↓|β1. |πLet |εP|4α=↓|4p|gk. |πBy
8918 Algorithm R we may write |εq(x)|4α=↓|4a|β0|4α+↓|4Pa|β1x|4α+↓
8923 |1|1|¬O|4|¬O|4|¬O|1|1α+↓|4P|gsa|βsx|gs, |πwhere
8925 |εs|4α=↓|4m|4α_↓|4n|4|¬R|42. |πLet us look at
8930 the coe∃cients of |εx|gn|gα+↓|g1, x|gn, |πand
8936 |εx|gn|gα_↓|g1 |πin |εv(x)q(x), |πnamely |εPa|β1v|βn|4α+↓|4P
8940 |g2a|β2v|βn|βα_↓|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|4,
8941 a|β0v|βn|4α+↓|4Pa|β1v|βn|βα_↓|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|4,
8942 a|β0v|βn|βα_↓|β1|4α+↓|4Pa|β1v|βn|βα_↓|β2|4α+↓|1|1|¬O|4|¬O|4|
8942 ¬O|4, |πeach of which is a multiple of |εP|g3.
8951 |πWe conclude from the _rst that |εp|gj|¬Da|β1,
8958 |πfrom the second that |εp|ur|πmin(|εk,2j)|)|)|¬Da|β0,
8963 |πthen from the third that |εP|¬Da|β0. |πHence
8970 |εP|¬Dr(x). |π[If |εm |πwere only |εn|4α+↓|41,
8976 |πthe best we could prove would be that |εp|ur|"pk/2|"P|)|)
8985 |πdivides |εr(x); |πe.g., consider |εu(x)|4α=↓|4x|g3|4α+↓|41
8989 , v(x)|4α=↓|44x|g2|4α+↓|42x|4α+↓|41, r(x)|4α=↓|418.
8992 |πBy considering an algorithm for computing polynomial
8999 resultants, W. S. Brown has generalized this
9006 exercise in a di=erent way (to appear).]|'|H*?*?{U0}{H9L11M29}
folio 800 galley 13
9013 58320#Computer Programming!(Knuth/A.-W.)!Ch.
9015 4!f. 800!g. 13c|'{A12}|≡1|≡5|≡.|4|9Let |εc|βi|βj|4α=↓|4a|βi|
9019 β1a|βj|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|βi|βna|βj|βn;
9020 |πwe may assume that |εc|βi|βi|4|¬Q|40 |πfor
9026 all |εi. |πIf |εc|βi|βj|4|=|↔6α=↓|40 |πfor some
9032 |εi|4|=|↔6α=↓|4j, |πwe can replace row |εi |πby
9039 |ε(a|βi|β1|4α_↓|4ca|βj|β1,|4.|4.|4.|4,|4a|βi|βn|4α_↓|4ca|βj|
9039 βn), |πwhere |εc|4α=↓|4c|βi|βj/c|βj|βj; |πthis
9043 does not change the value of the determinant,
9051 and it decreases the value of the upper bound
9060 we wish to prove, since |εc|βi|βi |πis replaced
9068 by |εc|βi|βi|4α_↓|4c|ur2|)ij|)/c|βi|βj. |πThese
9071 replacements can be done in a systematic way
9079 for increasing |εi |πand for |εj|4|¬W|4i, |πuntil
9086 |εc|βi|βj|4α=↓|40 |πfor all |εi|4|=|↔6α=↓|4j.
9090 |π(The latter algorithm is called ``Schmidt's
9096 orthogonalization process''; see |εMath. Annalen
9101 |≡6|≡3 (1907), 442.) |πThen det|ε(A)|g2|4α=↓|4det(|εAA|gT)|4
9105 α=↓|4c|β1|β1|4.|4.|4.|4c|βn|βn.|'{A3}{H9L11M29}|π|≡1|≡6|≡.|4
9106 |9Let |εf|1(x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|4g|βm(x|β2,|4.|4.|
9107 4.|4,|4x|βn)x|urm|)1|)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4g|β0(x|
9107 β2,|4.|4.|4.|4,|4x|βn), |πand let |εg(x|β2,|4.|4.|4.|4,|4x|β
9110 n)|4α=↓|4g|βm(x|β2,|4.|4.|4.|4,|4x|βn)|g2|4α+↓|1|1|¬O|4|¬O|4
9110 |¬O|1|1α+↓|4g|β0(x|β2,|4.|4.|4.|4,|4x|βn)|g2;
9111 |πthe latter is not identically zero. We have
9119 |εa|βN|4|¬E|4m(2N|4α+↓|41)|gn|gα_↓|g1|4α+↓|4(2N|4α+↓|41)b|βN
9119 , |πwhere |εb|βN |πis the number of integer solutions
9128 of |εg(x|β2,|4.|4.|4.|4,|4x|βn)|4α=↓|40 |πwith
9131 variables bounded by |εN. |πHence lim|ε|βN|β|¬L|β|¬X|4a|βN/(
9136 2N|4α+↓|41)|gn|4α=↓|4|πlim|ur|ε|)N|¬L|¬X|)|4b|βN/(2N|4α+↓|41
9136 )|gn|gα_↓|g1, |πand this is zero by induction.|'
9143 {A3}|≡1|≡7|≡.|4|9a) For convenience, let us describe
9149 the algorithm only for |εA|4α=↓|4|¬Ta,|4b|¬Y.
9154 |πThe hypotheses imply that deg(|εQ|β1U)|4α=↓|4|πdeg(|εQ|β2V
9158 )|4|¬R|40, |πand deg(|εQ|β1)|4|¬E|4|πdeg(|εQ|β2).
9161 |πIf deg(|εQ|β1)|4α=↓|40, |πthen |εQ|β1 |πis
9166 must a nonzero rational number, so we set |εQ|4α=↓|4Q|β2/Q|β
9174 1. |πOtherwise let |εQ|β1|4α=↓|4aQ|β1|β1|4α+↓|4bQ|β1|β2|4α+↓
9177 |4r|β1, Q|β2|4α=↓|4aQ|β2|β1|4α+↓|4bQ|β2|β2|4α+↓|4r|β2,
9179 |πwhere |εr|β1 |πand |εr|β2 |πare rational numbers;
9186 it follows that|'{A9}|εQ|β1U|4α_↓|4Q|β2V|4α=↓|4a(Q|β1|β1U|4α
9189 _↓|4Q|β2|β1V)|4α+↓|4b(Q|β1|β2U|4α_↓|4Q|β2|β2V)|4α+↓|4r|β1U|4
9189 α_↓|4r|β2V.|;{A9}|πWe must have either deg(|εQ|β1|β1)|4α=↓|4
9194 |πdeg(|εQ|β1)|4α_↓|41 |πor deg(|εQ|β1|β2)|4α=↓|4|πdeg(|εQ|β1
9196 )|4α_↓|41. |πIn the former case, deg|ε(Q|β1|β1U|4α_↓|4Q|β2|β
9201 1V)|4|¬W|4|πdeg(|εQ|β1|β1U), |πby considering
9204 the terms of highest degree which start with
9212 |εa; |πso we may replace |ε(Q|β1, Q|β2) |πby
9220 |ε(Q|β1|β2, Q|β2|β2) |πand repeat the process.|'
9226 !!|1|1b) We may assume that deg(|εU)|4|¬R|4|πdeg(|εV).
9232 |πIf deg(|εR)|4|¬R|4|πdeg(|εV), |πnote that |εQ|β1U|4α_↓|4Q|
9236 β2V|4α=↓|4Q|β1R|4α_↓|4(Q|β2|4α_↓|4Q|β1Q)V |πhas
9238 degree less than deg(|εV)|4|¬E|4|πdeg(|εQ|β1R),
9242 |πso we can repeat the process with |εU |πreplaced
9251 by |εR; |πwe obtain |εR|4α=↓|4Q|¬SV|4α+↓|4R|¬S,
9256 U|4α=↓|4(Q|4α+↓|4Q|¬S)V|4α+↓|4R|¬S, |πwhere deg(|εR|¬S)|4|¬W
9258 |4|πdeg(|εR), |πso eventually a solution will
9264 be obtained.|'!!|1|1c) The algorithm of (b) gives
9272 |εV|β1|4α=↓|4UV|β2|4α+↓|4R, |πdeg(|εR)|4|¬W|4|πdeg|ε(V|β2);
9274 |πby homogeneity |εR|4α=↓|40 |πand |εU |πis homogeneous.|'
9281 !!|1|1d) We may assume that deg|ε(V)|4|¬E|4|πdeg(|εU).
9287 |πIf deg(|εV)|4α=↓|40, |πset |εW|4|¬L|4U; |πotherwise
9292 use (c) to _nd |εU|4α=↓|4QV, |πso that |εQVV|4α=↓|4VQV,
9300 (QV|4α_↓|4VQ)V|4α=↓|40. |πThis implies that |εQV|4α=↓|4VQ,
9305 |πso we can set |εU|4|¬L|4V, V|4|¬L|4Q |πand
9312 repeat the process.|'!!|1|1For further details
9318 about the subject of this exercise, see P. M.
9327 Cohn, |εProc. Cambridge Phil. Soc. |≡5|≡7 (1961),
9334 18<30. |πThe considerably more di∃cult problem
9340 of characterizing |εall |πstring polynomials
9345 such that |εUV|4α=↓|4VU |πhas been solved by
9352 G. M. Bergman [Ph.D. thesis, Harvard University,
9359 1967].|'{A3}|≡1|≡8|≡.|4|9[P. M. Cohn, |εTransactions
9364 Amer. Math. Soc. |≡1|≡0|≡9 (1963), 332<356.]|'
9370 {A3}{I3H}|π!!|1|1|≡C|≡1|≡.|9Set |εu|β1|4|¬L|4U|β1,
9372 u|β2|4|¬L|4U|β2, v|β1|4|¬L|4V|β1, v|β2|4|¬L|4V|β2,
9375 z|β1|4|¬L|4z|ur|↔0|)2|)|4|¬L|4w|β1|4|¬L|4w|ur|↔0|)2|)|4|¬L|4
9375 1, z|ur|↔0|)1|)|4|¬L|4z|β2|4|¬L|4|¬L|4w|ur|↔0|)1|)|4|¬L|4w|β
9376 2|4|¬L|40, n|4|¬L|40.|'{A3}|π!!|1|1|≡C|≡2|≡.|9(At
9379 this point the identities given in the exercise
9387 hold, and also |εu|β1v|β1|4α=↓|4u|β1v|β2; v|β2|4α=↓|40
9392 |πif and only if |εu|β1|4α=↓|40.) |πIf |εv|β2|4α=↓|40,
9399 |πthe algorithm terminates with gcrd(|εV|β1,
9404 V|β2)|4α=↓|4v|β1, |πlclm(|εV|β1, V|β2)|4α=↓|4z|ur|↔0|)1|)V|β
9406 1|4α=↓|4|→α_↓z|ur|↔0|)2|)V|β2. (|πAlso by symmetry
9410 gcld(|εU|β1, U|β2)|4α=↓|4|πlclm(|εU|β1, U|β2)|4α=↓|4U|β1w|β1
9412 |4α=↓|4|→α_↓U|β2w|β2.)|'{A3}|1|1!!|π|≡C|≡3|≡.|9Find
9414 |εQ |πand |εR |πsuch that |εv|β1|4α=↓|4Qv|β2|4α+↓|4R,
9420 |πwhere deg(|εR)|4|¬W|4|πdeg(|εv|β2). {H11}({H9}|πWe
9423 have |εu|β1(Qv|β2|4α+↓|4R)|4α=↓|4u|β2v|β2, |πso
9426 |εu|β1R|4α=↓|4(u|β2|4α_↓|4u|β1Q)v|β2|4α=↓|4R|¬Sv|β2.{H11}){H
9426 9}|'{A3}!!|1|1|π|≡C|≡4|≡.|4|9Set (|εw|β1, w|β2,
9430 w|ur|↔0|)1|), w|ur|↔0|)2|), z|β1, z|β2, z|ur|↔0|)1|),
9435 z|ur|↔0|)2|), u|β1, u|β2, v|β1, v|β2)|4|¬L|4(w|ur|↔0|)1|)|4α
9439 _↓|4w|β1Q, w|ur|↔0|)2|)|4α_↓|4w|β2Q, w|β1, w|β2,
9443 z|ur|↔0|)1|), z|ur|↔0|)2|), z|β1|4α_↓|4Qz|ur|↔0|)1|),
9446 z|β2|4α_↓|4Qz|ur|↔0|)2|), u|β2|4α_↓|4u|β1Q, u|β1,
9449 v|β2, v|β1|4α_↓|4Qv|β2) |πand |εn|4|¬L|4n|4α+↓|41.
9453 |πGo back to C2.|'|Hβ*?*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
9457